csu 1092 大尾巴狼

最近的任务是最短路，白书上的内容勉强能懂，一到做题就完了蛋了。这毕竟是具体的算法，不像DP只是思想，没有基础真的不行，于是学长让我先做并查集，再看树，再学图论……

说到并查集，有篇很经典的文章http://apps.hi.baidu.com/share/detail/15881874，要是讲算法的文章都是这种风格，那世界就太美好了。

代码如下：

 1 #include<stdio.h>
 2 int boss[10000010];
 3 int n,m;
 4 int find(int a)
 5 {
 6     int i,j,r;
 7     r = i = a;
 8     while(boss[r] != r)
 9         r = boss[r];
10     while(i != r)
11     {
12         j = boss[i];
13         boss[i] = r;
14         i = j;
15     }
16     return r;
17 }
18 int main()
19 {
20     int i,t1,t2,b1,b2,ans;
21     while(~scanf("%d%d",&n,&m))
22     {
23         for(i = 1; i <= m; i++)
24             boss[i] = i;
25         ans = 0;
26         for(i = 0; i < n; i++)
27         {
28             scanf("%d%d",&t1,&t2);
29             b1 = find(t1);
30             b2 = find(t2);
31             if(b1 != b2)
32                 boss[b2] = b1;
33         }
34         int t = find(1);
35         for(i = 2; i <= m; i++)
36             if(find(i) == t)
37                 ans++;
38         printf("%d\n",ans);
39     }
40     return 0;
41 }