#include <iostream>#include <cstdio>#include <cstring>#define maxlen 1100using namespace std;bool maps[maxlen][maxlen];int visited[maxlen];int n,m;void dfs(int i){    if(visited[i])        return ;     visited[i]=true;     for(int j=1;j<=n;++j)     {         if(maps[i][j]==true&&!visited[j])         {             dfs(j);         }    } } int main (){     int a,b;     while(scanf("%d%d",&n,&m)!=EOF)     {         for(int i=0;i<=n;++i)         for(int j=0;j<=n;++j)         {             if(i==j)                 maps[i][j]=1;             else                maps[i][j]=0;        }         for(int i=0;i<m;++i)        {             scanf("%d%d",&a,&b);             maps[a][b]=maps[b][a]=true;         }         memset(visited,0,sizeof(visited));         int ans=0;         for(int i=1;i<=n;++i)         {             if(!visited[i])             {                 dfs(i);                 ans++;             }         }       printf("%d\n",ans);     } }

超级无敌张小豪是A国的一名勇士,A国的勇士都要靠获得能量变得更强,在A国勇士获得能量只有唯一的一种途径就是膜拜宙斯神——周尼玛(桑！！！)。要膜拜周尼玛就要去到遥远的大日国那里有好多好多周尼玛(桑！！！)。但是周尼玛（桑！！！）是一种群居动物，一队周尼玛（桑！！！）中都有且只有一个领袖叫周尼玛你妹（桑！！！）超级无敌张小豪勇士必须拿着一炷香到周尼玛你妹（桑！！！）面前膜拜三下即可获得一点能量。

膜拜必须遵循一些规则：

对于一个周尼玛你妹（桑！！！）只能膜拜一次；

不能膜拜周尼玛（桑！！！）；

一次膜拜用一炷香且一炷香只能膜拜一次；

现在问题出现了，小豪准备启程去大日国，在走之前小豪要准备买香但是小豪不知道大日国一共有几队周尼玛（桑！！！），小豪既想每个周尼玛你妹（桑！！！）都膜拜到，又想带过去的香能用完不浪费。于是小豪打听小道消息搞过来了一张周尼玛（桑！！！）家族谱。

家族谱上有若干对数字

eg：1 2

    2 4

表示：周尼玛1号和周尼玛2号是一队的

      周尼玛2号和周尼玛4号是一队的

若谱上告诉你周尼玛x号和周尼玛y号是一队的周尼玛y号和周尼玛z号是一队的

那也就代表了周尼玛x号和周尼玛z号是一队的了。

The input starts with an integer T(1<=T<=10) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N<= 30000,1<=M<= 500000). N indicates the number of周尼玛, the 周尼玛 are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means 周尼玛 A号 and 周尼玛 B号 in the same team. There will be a blank line between two cases.

For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks. 

#include <iostream>using namespace std;const int N=30000;int flag[N];int Find_Set(int x){    if(x!=flag[x])    {        flag[x]=Find_Set(flag[x]);    }    return flag[x];}int main(){    int t,m,n,i,j,a,b,A,B,num;    cin>>t;    while(t--)    {        cin>>n>>m;        for(i=1;i<=n;i++) flag[i]=i;        num=n;        for(i=1;i<=m;i++)        {            cin>>A>>B;            a=Find_Set(A);            b=Find_Set(B);            if(a>b)            {                flag[a]=b;                num--;            }            else if(a<b)            {                flag[b]=a;                num--;            }        }        cout<<num<<endl;    }    return 0;}

　　然后再倒过来再考虑一下能否用并查集搞定无向图的连通支路？

#include <iostream>#include <string.h>using namespace std;const int N=30000;int flag[N];int Find_Set(int x){    if(x!=flag[x])    {        flag[x]=Find_Set(flag[x]);    }    return flag[x];}int main(){    int t,m,n,i,j,a,b,A,B,num;    while(scanf("%d%d",&n,&m)!=EOF)    {    	memset(flag,0,sizeof(flag));     	for(i=1;i<=n;i++) flag[i]=i;        num=n;        for(i=1;i<=m;i++)        {            cin>>A>>B;            a=Find_Set(A);            b=Find_Set(B);            if(a>b)            {                flag[a]=b;                num--;            }            else if(a<b)            {                flag[b]=a;                num--;            }        }        cout<<num<<endl;    	}	return 0;}

　　就这样搞定了.....突然觉得我真不是搞ACM的材料.....妈蛋