重剑无锋
我生待明日,万事成蹉跎
posts - 13,  comments - 6,  trackbacks - 0
我会继续更新这个东西,慢慢努力。
这次写的是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>
 8void 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 阅读(599) 评论(0)  编辑 收藏 引用 所属分类: Data Structure

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2012年12月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿

随笔分类

随笔档案

friends

  • figoSB
  • 除了我...谁敢叫韩飞sb...

搜索

  •  

最新评论

阅读排行榜

评论排行榜