数据结构_并查集.cpp

来自「一些ACM基本算法的测试源码」· C++ 代码 · 共 43 行

#include<iostream>
using namespace std;

const int MAXN = 1000001;
int p[MAXN]; 

void makeset(int n)
{
    for(int i = 1; i <= n; i ++)
        p[i] = i;     
}

int find(int x)
{
    if(p[x] != x)  p[x] = find(p[x]);
    return p[x];    
}

void unionone(int i, int j)
{
    if(find(i) != find(j))
        p[find(i)] = find(j);     
}

int main()
{
    int n, m, a, b;
    cin >> n >> m;
    makeset(n);
    for(int i = 0; i < m; i ++)
    {
        cin >> a >> b;
        if(find(a) != find(b))
            unionone(a, b);    
    }   
    for(int i = 1; i <= n; i ++)
    {
        cout << find(i) << endl;        
    } 
    system("pause");
    return 0;
}