题解 P2839 【畅通工程】

ghj1222 · 2016-09-07 14:05:31 · 题解

发一个简单的，大家都能看懂的

#include <iostream>
using namespace std;
int f[1001];
int getf(int x)//经典的递归找爹+路径压缩
{
    return f[x]==x?x:f[x]=getf(f[x]);
}
int main()
{
    int n,m,t1,t2,ans=-1;//为什么ans=-1呢？
    cin >> n >> m;
    for(int i=1;i<=n;i++)//并查集初始化
        f[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin >> t1 >> t2;//读入
        f[getf(t1)]=getf(t2);//合并并查集
    }
    for(int i=1;i<=n;i++)
        if(f[i]==i)ans++;//如果某一个节点的父亲是自己，说明他带领了一个连通块儿
    cout << ans << endl;
    return 0;
}