Hdu 1829-A Bug's Life(并查集初试水)

链接如下:
Problem - 1829

这是第二天的英语编程练习题,这次用到了并查集的一部分思想(盗版并查集哈).重点在于找到根,这样会更好比较,比如1->2,2->3,3->4,4->5,那么3,5都可作为1类型,4则可做为2类型,如果发现同种类型在一起,那就发现可疑.

话不多说,生词代码奉.

---

interact 互动,相互作用,相互影响.

scenarios 情节,剧本,脚本.

distinct 明显的,清楚的,卓越的.

consecutively 连续地;

---

#include<stdio.h>

#include<map>

using namespace std;

map<int,int> mp;

int find(int a,int b){

int c=a,d=b;

if(mp[a]==0) mp[a]=b;

if(mp[b]==0) mp[b]=a;

while(a!=mp[mp[a]]){

a=mp[a];

a=mp[a];

}

while(b!=mp[mp[b]]){

b=mp[b];

b=mp[b];

}

if(a!=b){

mp[c]=b;

mp[d]=a;

return 0;

}

else return 1;

}

int main()

{

int n;

scanf("%d",&n);

for(int i=1;i<=n;i++){

int flag=1;

int scenarios,interactions;

scanf("%d %d",&scenarios,&interactions);

    mp.clear();

    while(interactions--){

    int act1,act2;

    scanf("%d %d",&act1,&act2);

    if(find(act1,act2)) flag=0;

    }

if(flag==0) printf("Scenario #%d:\nSuspicious bugs found!\n",i);

else printf("Scenario #%d:\nNo suspicious bugs found!\n",i);

printf("\n");

}

return 0;

}