随笔-65  评论-6  文章-0  trackbacks-0
 1 #include <cstdio>
 2 #include <cstdlib> //加这两个头文件比<iostream>省空间
 3 using namespace std;
 4 #define MAXSIZE    2005
 5 int oppo[MAXSIZE],par[MAXSIZE];
 6 int yes;
 7 char c;
 8 
 9 void makeSet(int n){
10     int i;
11     for(i=0;i<=n;i++)
12         oppo[i]=-1,par[i]=i;
13     yes=1;
14 }
15 int findSet(int x){
16     if(x!=par[x])
17         par[x]=findSet(par[x]);
18     return par[x];
19 }
20 void merge(int x,int y){
21     par[findSet(x)]=findSet(y);
22 }
23 inline void scan(int &x){
24     while(c=getchar(),c<'0'||c>'9');x=c-'0';
25     while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';    
26 }
27 
28 int main(){
29     int t,no=1;
30     //scanf("%d",&t);
31     scan(t);//recommend this style of input,faster than scanf()
32     while (t--){
33         int n,m;//the number of bugs And the interactions
34         scan(n);scan(m);
35         int i,j;
36         makeSet(n);
37         for(i=0;i<m;i++){
38             int a,b;
39             scan(a);scan(b);
40             if(yes){
41                 if (oppo[a]==-1&&oppo[b]==-1){// a b both appear at first time
42                     oppo[a]=b;oppo[b]=a;
43                 }
44                 else if (oppo[a]==-1){
45                     oppo[a]=b;merge(a,oppo[b]);
46                 }
47                 else if (oppo[b]==-1){
48                     oppo[b]=a;merge(b,oppo[a]);
49                 }
50                 else{
51                     if (findSet(a)==findSet(b))
52                         yes=0;
53                     else{
54                         merge(a,oppo[b]);
55                         merge(b,oppo[a]);
56                     }
57                 }
58             }
59         }
60         printf("Scenario #%d:\n",no++);
61         printf(yes?"No suspicious bugs found!":"Suspicious bugs found!");
62         printf("\n\n");
63     }
64     return 0;
65 }
posted on 2012-03-16 14:42 Leo.W 阅读(352) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理