UVa 13153. Number of Connected Components

Description

給你 N 個節點，每個點上附有一個介於$1～10^6$之間的正整數。假如某2個節點上的數其最大公因數（GCD）大於1，則這2個節點之間會有一條邊存在。
要請你算出這N個節點構成的的圖形中，共有幾個連通的單元。

Input Format

輸入的第一列有一個正整數t代表以下有幾筆測資。（$t \le 100$）
每筆測資的第一列，有一個正整數 N（$1 \le N \le 10^5$），代表節點的數目。接下來的一列含有N個正整數，代表這N個節點上面附帶的數。

Output Format

對每筆測資輸出一列，先輸出這是第幾筆測資，然後輸出這N個節點構成的圖形中，共有幾個連通的單元。

Sample Input

2
3
2 3 4
6
2 3 4 5 6 6

Sample Output

Case 1: 2
Case 2: 2

UVa - 13153
翻譯來源：Luckycat

Solution

這題有兩個想法，第一就是對點$i, j(i,j \in 輸入 \text{ 且 } i \neq j)$ 去做Disjoint set，時間複雜度為$O(N^2)$。
如果是這樣做的話，一定會TLE，所以我們要去思考另一種做法：
題目是跟我們說 $\text{最大公因數} > 1$的兩點要連起來，不妨試試將點和點的連接換成質數的連接，每輸入一個數字n，就將n所有的質因數連起來，輸入結束之後再算共有幾個集合即可。
注意！題目有可能會輸入重複數字，若為1，則需特別考慮。

Code

/*************************************************************************
  > File Name: 13153 - Number of Connected Components.cpp
  > Author: Samuel
  > Mail: enminghuang21119@gmail.com
  > Created Time: Tue Jul 24 19:59:14 2018
*************************************************************************/

#include <bits/stdc++.h>
using namespace std;

bool tmp[1000000];
int parent[1000000];
vector<int> p;
int usenum[1000000];
int n, cnt, size, num;

int find_parent(int i) {
    if (i == parent[i])
        return i;
    return parent[i] = find_parent(parent[i]);
}

void connect(int a, int b) {
    int pa = find_parent(a);
    int pb = find_parent(b);
    if (pa == pb)
        return;
    parent[pb] = pa;
}

void factorization(int i) {
    int first = 0;
    int a = 2;
    for (int j = 0; a <= sqrt(i); a = p[++j])
        if (!(i % a)) {
            if (!tmp[a]) {
                usenum[num++] = a;
                parent[a] = a;
            }
            tmp[a] = 1;
            if (!first)
                first = a;
            else {
                connect(first, a);
            }
            while (!(i % a)) 
                i /= a;
        }
    if (i > 1) {
        if (!tmp[i]) {
            usenum[num++] = i;
            parent[i] = i;
        }
        tmp[i] = 1;
        if (first)
            connect(first, i);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    tmp[2] = 1;
    p.push_back(2);
    for (int i = 3; i < 1000; i += 2) {
        if (tmp[i])
            continue;
        p.push_back(i);
        for (int j = i << 1; j < 1000; j += i)
            tmp[j] = 1;
    }
    p.push_back(1 << 30);
    int c;
    cin >> c;
    for (int i = 1; i <= c; i++) {
        cin >> n;
        memset(tmp, 0, sizeof(tmp));
        num = cnt = 0;
        while (n--) {
            int i;
            cin >> i;
            if (i == 1)
                cnt++;
            else
                factorization(i);
        }
        for (int i = 0; i < num; i++) {
            int t;
            if (tmp[t = find_parent(usenum[i])])
                tmp[t] = 0, cnt++;
        }
        cout << "Case " << i << ": " << cnt << '\n';
    }
    return 0;
}