我会继续更新这个东西，慢慢努力。
这次写的是poj上面的写过的一个并查集，但是可能水平高了一些。
这道题目的收获，一定要搞清楚逻辑关系，只有这样才能够不落下一种情况，这种情况多的问题，一定要处理好所有的情况。
关于并查集说了好多了，这个并查集就是一颗大树，每个元素都有和父母的关系，然后维护这个关系。
1
#include<iostream>
2#include<cstdio>
3using namespace std;
4const int maxnum=2000+1;
5int G[maxnum],num[maxnum];
6#define re1(i,n) for(int i=(1);i<=(n);++i)
7template<class T>
8
void show(T *a,int n,int m)
{
9
for(int i=n;i<=m;i++)
10 cout<<a[i]<<' ';
11 cout<<endl;
12
}
13int find(int x){
14 int u=G[x];
15
if(u!=x){
16 G[x]=find(u);
17 num[x]=(num[x]+num[u])%2;
18
}
19 return G[x];
20}
21void u3n(int a,int b){
22 int x=find(a);
23 int y=find(b);
24 G[x]=b;
25 if(num[a]==0)
26 num[x]=1;
27 else
28 num[x]=0;
29
30}
31int main(){
32 // #define home gggin
33 #ifdef home
34 freopen("7.txt","r",stdin);
35 #endif
36 int tcase,tnum=0;
37 scanf("%d",&tcase);
38 while(tcase--){
39 int n,m;
40 ++tnum;
41 scanf("%d%d",&n,&m);
42 re1(u,n){
43 G[u]=u;
44 num[u]=0;
45 }
46 bool flag=true;
47 re1(u,m){
48 int t1,t2;
49 scanf("%d%d",&t1,&t2);
50 if(find(t1)==find(t2) && num[t1]==num[t2])
51 flag=false;
52 else if(find(t1)!=find(t2)){
53 u3n(t1,t2);
54 }
55 }
56 //show(G,1,3);
57 //show(num,1,3);
58 if(!flag)
59 printf("Scenario #%d:\nSuspicious bugs found!",tnum);
60 else
61 printf("Scenario #%d:\nNo suspicious bugs found!",tnum);
62 printf("\n\n");
63 }
64}
65
posted on 2012-12-09 23:32
Gin 阅读(601)
评论(0) 编辑 收藏 引用 所属分类:
Data Structure