写在题目前:
通过这道题我深深的明白了洛谷在某些题目方面的匮乏,比如带权并查集,只有一题。
那么我解决的方法是: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