HDU 1232 畅通工程

Description

Input

Output

Sample Input

Sample Output

102998Union-Find Sets;LANGUAGE:C++CODE:
#include<iostream>#include<cstdio>#define MAX 1005using namespace std;int father[MAX];int rank[MAX];void Make_Set(int x){    father[x] = x;    rank[x] = 0;}int Find_Set(int x){    if (x != father[x])    {        father[x] = Find_Set(father[x]);    }    return father[x];}void Union(int x, int y){    x = Find_Set(x);    y = Find_Set(y);    if (x == y) return;    if (rank[x] > rank[y])    {        father[y] = x;    }    else    {        if (rank[x] == rank[y])        {            rank[y]++;        }        father[x] = y;    }}int main(){    //freopen("in.txt","r",stdin);    int n,m,i,a,b,t;    cin>>t;    while(t--)    {        cin>>n>>m;        for(i=1;i<=n;i++)        {            Make_Set(i);        }        for(i=1;i<=m;i++)        {            cin>>a>>b;            Union(a,b);        }        int flag;        for(i=1;i<=n;i++)        {            flag=Find_Set(i);            rank[flag]=-1;        }        int ans=0;        for(i=0;i<=n;i++)        {            if(rank[i]==-1)            ans++;        }        cout<<ans<<endl;;    }    return 0;}