A Bug's Life

Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 8528    Accepted Submission(s): 2745

2

3 3

1 2

2 3

1 3

4 2

1 2

3 4

Scenario #1:

Suspicious bugs found!

Scenario #2:

No suspicious bugs found!

Hint

Huge input,scanf is recommended.

利用黑白染色，推断是否是二分图。

#include"stdio.h"

#include"string.h"

#include"queue"

using namespace std;

#define N 2005

#define M 1000005

int n,m,t,head[N];

int color[N],flag;

struct node

{

    int u,v,next;

}map[2*M];

void add(int u,int v)

{

    map[t].u=u;

    map[t].v=v;

    map[t].next=head[u];

    head[u]=t++;

    map[t].u=v;

    map[t].v=u;

    map[t].next=head[v];

    head[v]=t++;

}

void find(int u)

{

    int i,v;

    for(i=head[u];i!=-1;i=map[i].next)

    {

        v=map[i].v;

        if(color[v]==-1)

        {

            color[v]=color[u]^1;

            find(v);

        }

        else if(color[v]==color[u])

        {

            flag=1;

            return ;

        }

    }

    return ;

}

int main()

{

    int i,T,u,v,cnt=1;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        t=0;

        memset(head,-1,sizeof(head));

        while(m--)

        {

            scanf("%d%d",&u,&v);

            add(u,v);

        }

        memset(color,-1,sizeof(color));

        flag=0;

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

        {

            if(color[i]==-1)

            {

                color[i]=0;

                find(i);

                if(flag)

                    break;

            }

        }

        printf("Scenario #%d:\n",cnt++);

        if(flag)

            printf("Suspicious bugs found!\n");

        else

            printf("No suspicious bugs found!\n");

        puts("");

    }

    return 0;

}

带权并查集：

#include"stdio.h"

#include"string.h"

#include"queue"

#include"vector"

#include"stack"

#include"algorithm"

using namespace std;

#define N 2005

#define min(a,b) (a<b?a:b)

int pre[N],gen[N];

int find(int k)

{

    if(k==pre[k])

        return k;

    int t=find(pre[k]);     //不能马上更新父节点与根节点同样

    gen[k]=gen[k]^gen[pre[k]];//由于该节点的性别和它的父节点相反

    return pre[k]=t;  //确定该点性别之后才干把该点父节点更新为根节点

}

int Union(int x,int y)

{

    int a,b;

    a=find(x);

    b=find(y);

    if(a==b)       //x,y的根节点同样

    {

        if(gen[x]==gen[y]) //推断他们是否同性别

            return 1;

        return 0;

    }

    pre[a]=b;

    gen[a]=(gen[x]+gen[y]+1)&1;

    return 0;

}

int main()

{

    int i,u,v,n,cnt=1,T,m;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(i=0;i<=n;i++)

            pre[i]=i;

        memset(gen,0,sizeof(gen));

        int flag=0;

        while(m--)

        {

            scanf("%d%d",&u,&v);

            if(flag)

                continue;

            flag=Union(u,v);

        }

        printf("Scenario #%d:\n",cnt++);

        if(flag)

            printf("Suspicious bugs found!\n");

        else

            printf("No suspicious bugs found!\n");

        puts("");

    }

    return 0;

}