这是一道考查并查集的题目，什么是并查集？并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

这道题目的主要意思是：（按输入样例来讲解），第一行的 5（N）和10（M）代表着 有5个城市，10条城市之间的路线，接着的10行代表着每一条路线，例如：0 1 -> 0这个城市与1这个城市有一条路线能走。

输出（Output M lines, the ith line is the answer after deleting the firsti edges in the input.）

意思为有输出M行（即有多少条路线就输出多少个结果），每行是指当前行的路线以及之前的路线都被切断而造成独立的整体一共有多少个，独立的整体是指：假如有5个城市，每个城市之间都没有路线连通，那么独立的整体就有5个，假如有一条路线连通了两个城市，其他3个城市都是独立的，那么独立的整体一共就有4个，以此类推，假如5个城市都被连通了，那么独立的整体就只有1个了。

根据题意，我觉得逆序处理比较容易，画个图你就明白了

下面5个点代表5个城市分别是（0,1,2,3,4）

此时有5个独立整体，即测试样例里面最后一组数据（2,4）已经之前的数据（路线）都被切断，那么5个城市之间都没有路线连通，就有5个独立的整体（2,4 -> 5）

我们逆序来推导，当有2,4这条路线的时候

那么有两个城市被连通了，那么剩下4个独立整体（3,4 -> 4）

再往上，当3,4还有的时候，同样

那么2 3 4城市都被连通，成为一个整体，那么剩下3个独立整体（0,3 -> 3）

往上是同样的道理，相信大家都能自己推导出来

现在大家都理解了题意之后，怎么去解决这道题呢

利用并查集啊！

思路如下：

构建递归树查出每加一条路线的两个城市的父节点是否是相同，

如果相同，那么对所有独立的整体没有丝毫影响，

比如（有三条路线，分别是：

<路线①>福建去北京

<路线②>广州去北京

<路线③>上海去天津

此时有5个城市，独立整体有两个

如果加多一条<路线④> 广州去福建都之前的独立整体丝毫没有影响，依然是2个独立整体，

但是如果改变<路线④> 北京去天津 那么5个城市都连通了，独立整体就变成1个了

如果不相同，那么所加的这条路线是有意义的，能够使两个独立的整体变为一个，将总的独立整体数减一，并且将两

个不相同的父节点互相连接。

思路有了，那就开始写核心函数了

下面的函数是找父节点，

int findset(int x){

return fa[x]==-1?x:fa[x]=findset(fa[x]);

}

接着下面的函数是查询U,V两个城市的父节点是否一致，得出新增的路线有没有意义

int bind(int u,int v){

int fu=findset(u);

int fv=findset(v);

if(fu==fv)

return 0;

else{

fa[fu]=fv;

return 1;

}

}

不明白？！！不怕，我一步步用测试样例讲到明白（输入，输出，逆序）

第一步：初始化     fa数组用来存储每个城市对应的父节点

fa[]：

fa[0]

fa[1]

fa[2]

fa[3]

fa[4]

-1

-1

-1

-1

-1

cnt：5      (逆序来：一开始5个城市都是独立的)

-------------------------------------------------------------------------------------------------------------------------------

第二步：2 4这条边留下，之前的边删除（反过来就是2 4加入）：调用bind(2,4)

fu=findset(2)：因为fa[2]==-1，所以返回2，即fu=2；

fv=findset(4)：因为fa[4]==-1，所以返回4，即fu=4；

因为fu!=fv，所以fa[2]=4；同时返回1；cnt-1值为4；

fa[]：

fa[0]

fa[1]

fa[2]

fa[3]

fa[4]

-1

-1

4

-1

-1

cnt：4 （由于2,4城市父节点不一样，所以新增路线有意义，独立整体数减一）

------------------------------------------------------------------------------------------------------

第三步：2 4和3 4边留下，之前的边删除（反过来就是2 4加入后，继续加入3 4）：在第二步的基础上调用bind(3,4)

fu=findset(3)：因为fa[3]==-1，所以返回3，即fu=3；

fv=findset(4)：因为fa[4]==-1，所以返回4，即fu=4；

因为fu!=fv，所以fa[3]=4；同时返回1；cnt-1值为3；

fa[]：

fa[0]

fa[1]

fa[2]

fa[3]

fa[4]

-1

-1

4

4

-1

cnt：3

------------------------------------------------------------------------------------------------------

第四步：2 4、3 4、03边留下，之前的边删除（反过来就是24加入后，加入34，继续加入03）：在第三步的基础上调用bind(0,3)

fu=findset(0)：因为fa[0]==-1，所以返回0，即fu=0；

fv=findset(3)：因为fa[3]!=-1，所以开始发生变化，这个时候要递归啦！

注意不是返回4，而是返回fa[x]=findset(fa[x])；返回的是findset(fa[x])，同时对fa[x]赋值为findset(fa[x])，此时x=3，所以这句话是fa[3]=findset(fa[3])，也就是fa[3]=findset(4)，各位看官请注意解。

继续findset(4)！此时的x=4，因为fa[4]==-1，所以返回4！

接下来做什么？把4赋值给fa[3]，同时把4作为最外层函数的返回值。注意这里的“把4赋值给fa[3]”看起来多余是因为现在这棵树只有两层，当超过两层时才会体现出价值！

最终fv=4。

因为fu!=fv，所以fa[0]=4；同时返回1；cnt-1值为2；

fa[]：

fa[0]

fa[1]

fa[2]

fa[3]

fa[4]

4

-1

4

4

-1

cnt：2

------------------------------------------------------------------------------------------------------

第五步：在第四步的基础上调用bind(0,4)

fu=findset(0)：因为fa[0]!=-1，这个时候又要开始递归！

此时x==0，fa[x]=findset(fa[x])其实是fa[0]=findset(4)；

继续：findset(4)的时候，因为x==4，fa[4]==-1，所以返回4

继续：fa[0]赋值为4，同时将4作为返回值赋值给fu

fv=findset(4) ：因为fa[4]==-1，所以返回4，即fv=4；

因为fu==fv，所以返回0；cnt值不变！

fa[]：

fa[0]

fa[1]

fa[2]

fa[3]

fa[4]

4

-1

4

4

-1

cnt：2

------------------------------------------------------------------------------------------------------

第六步：在第五步的基础上调用bind(2,3)

------------------------------------------------------------------------------------------------------

第七步：在第六步的基础上调用bind(0,2)

------------------------------------------------------------------------------------------------------

第八步：在第七步的基础上调用bind(1,4)

fu=findset(1)：因为fa[1]==-1，所以返回1，即fu=1；

fv=findset(4)：因为fa[4]==-1，所以返回4，即fu=4；

因为fu!=fv，所以fa[1]=4；同时返回1；cnt-1值为1；

fa[]：

fa[0]

fa[1]

fa[2]

fa[3]

fa[4]

4

4

4

4

-1

cnt：1

------------------------------------------------------------------------------------------------------

第九步：在第八步的基础上调用bind(1,3)

------------------------------------------------------------------------------------------------------

第十步：在第九步的基础上调用bind(1,2)

------------------------------------------------------------------------------------------------------

第十一步：在第十步的基础上调用bind(0,1)

注意：没有写出来的步骤都是fu==fv的情况，各位看官可以自己推导一下！

下面请看代码：

#include

#include

using namespace std;

int fa[10005];

int findset(int x){

return fa[x]==-1?x:fa[x]=findset(fa[x]);

}

int bind(int u,int v){

int fu=findset(u);

int fv=findset(v);

if(fu==fv)

return 0;

else{

fa[fu]=fv;

return 1;

}

}

int main(){

int num,cicties,path,i;

while(scanf("%d%d",&cicties,&path)==2){

memset(fa,-1,sizeof(fa));

vector<pair >vc;

for(i=0;i<=path-1;i++){

int x,y;

scanf("%d%d",&x,&y);

vc.push_back(make_pair(x,y));

}

vectorres;

int count=cicties;

res.push_back(count);

for(i=path-1;i>=0;i--){

count-=bind(vc[i].first,vc[i].second);

res.push_back(count);

}

for(i=res.size()-2;i>=0;i--)

printf("%d\n",res[i]);

}

return 0;

}

还有更多并查集的经典题目分别是

杭电OJ (acm.hdu.edu.cn)           北京大学OJ (poj.org)

基础部分

1、HDU 4496 D-City

2、HDU 1213 How Many Tables

3、HDU 1232 畅通工程

4、HDU 1325 Is It A Tree?

5、POJ 2524 Ubiquitous Religions

6、ZOJ 3321 Circle

7、HDU 1272 小希的迷宫

8、POJ 2236 Wireless Network

提高部分

1、POJ 1611 The Suspects

2、UVA 1329 Corporative Network

3、POJ 1182 食物链

这题：属于“并查集路径压缩”的经典题，关键点在于：在原始并查集的合并过程中增加了结点与根的关系的信息维护，同时注意一下，整个树的高度是不超过3层的，理论上所有结点都只与根有关系，只有在合并两个非叶子结点时才会出现3层，这也是路径压缩的意义所在。

4、HDU 3635 Dragon Balls

5、POJ 2494 ABug's Life

6、POJ 1703 Find them,Catch them