A Bug's Life

写在题目前:

通过这道题我深深的明白了洛谷在某些题目方面的匮乏,比如带权并查集,只有一题。

那么我解决的方法是:POJ!这是北京大学的OI网站,题目较全,但是是英文的,所以我上网查找了翻译。

本题链接:http://poj.org/problem?id=2492

POJ链接:http://poj.org/

本题就不放题面了(因为没有具体的中文题面)。

 

分析:

本题是带权并查集必刷题目之一,同时也是模板题,没有其他算法,只要套模板即可。然而蒟蒻我还是不会写。。。所以搬运了大佬的代码。

 

CODE:

 1 #include <cstdio>
 2 #include <cstring>
 3 int f[1111111],re[1111111];//re数组表示与其父节点的关系,1为不同性,0为同性 
 4 int find(int x){
 5     if (x!=f[x]){
 6         int t;
 7         t=f[x];
 8         f[x]=find(f[x]);
 9         re[x]=(re[x]+re[t])%2;
10     }
11     return f[x];
12 }
13 int main(){
14     int u;
15     int n,m;//n为总数,m为描述的个数
16     int num=1;
17     bool flag;
18     scanf ("%d",&u);
19     while (u--){
20         scanf ("%d %d",&n,&m);
21         for (int i=1;i<=n;i++)
22             f[i]=i;
23         memset(re,0,sizeof(re));
24         flag=false;
25         int x,y;
26         while (m--){
27             scanf ("%d %d",&x,&y);
28             int fx,fy;
29             fx=find(x);
30             fy=find(y);
31             if (fx!=fy){//如果根结点不同的话需要合并整理
32                 f[fy]=fx;
33                 re[fy]=(2-re[y]+re[x]+1)%2;
34             }
35             else{
36                 if (re[x]==re[y])
37                     flag=true;
38             }
39         }
40         printf ("Scenario #%d:\n",num++);
41         if (flag)
42             printf ("Suspicious bugs found!\n\n");
43         else
44             printf ("No suspicious bugs found!\n\n");
45     }
46     return 0;
47 }
48 //原文:https://blog.csdn.net/wyg1997/article/details/50623750 

 

 

 

上一篇:3.The significance of Books 书本的意义


下一篇:分享最好用的*邀请码55793939