[原创]HDU1829&POJ 2492 a bug's life [并查集||二分图染色]

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
const int M= 1005;
const int MAX= 100005;
const long long int MOD=1000000007;
using namespace std;
int pre[MAX];
int vis[MAX],n,m;
int color[MAX];//0  一个性别  1另一个性别
int ans=1,cnt,q,flag;
void ff(int n)
{
    for(int i=1; i<=n; i++)
    {
        pre[i]=i;
    }
    memset(color,0,sizeof(color));
    return ;
}

int findi(int x)    //理解，加强理解 
{
    int rt;
    if(x!=pre[x])
    {
        rt=findi(pre[x]);
        color[x]=color[x]^color[pre[x]];
        return pre[x]=rt;
    }
    return pre[x];
}

void join(int x,int y)
{
    int fx=findi(x),fy=findi(y);
    if(fx==fy)
    {
        ans=color[x]^color[y];
    }
    else
    {
        pre[fx]=fy;
        color[fx]=~(color[x]^color[y]);
    }

}

int main()
{
    int t,f=0;
    scanf("%d",&t);
    while(t--)
    {
        if(f==1)   printf("\n");
        f=1,ans=1;
        scanf("%d%d",&n,&m);
        ff(n);
        int a,b;
        for(int i=0;i<m;i++)
        {
            scanf("%d %d",&a,&b);
            if(ans)
            join(a,b);
        }

        printf("Scenario #%d:\n",++q);
        if(!ans)
            printf("Suspicious bugs found!\n");
        else
            printf("No suspicious bugs found!\n");

    }
    return 0;
}

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# include <vector>
# include <queue>
# define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;

const int N=2005;
int color
,n,m;
bool vis
;
vector<int> map
;

bool bfs(int s){
    queue<int> q;
    q.push(s);color[s]=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=1;i<=10000000;i++);
        printf("now %d\n",now);
        if(!vis[now]){
        int len=map[now].size();
        for(int i=0;i<len;i++){
            int des=map[now][i];
            q.push(des);
            if(color[des]==-1)
            color[des]=color[now]==0?1:0;
            else {
                if(color[des]==color[now]) return false;
                else continue;
            }
        }
        vis[now]=true;
        }
    }
    return true;
}

int main(){
    freopen("1.txt","r",stdin);
    int T,k=1;
    scanf("%d",&T);
    while(T--){
        CLR(color,-1);CLR(vis,0);
        CLR(map,0);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            map[a].push_back(b);
            map[b].push_back(a);
        }
        int i;
        printf("Scenario #%d:\n",k++);
        for(i=1;i<=n;i++){
            if(!vis[i]){
                bool flag=bfs(i);
                if(!flag){
                    printf("Suspicious bugs found!\n\n");
                    break;
                }
            }
        }
        if(i>n) printf("No suspicious bugs found!\n\n");
    }
    return 0;
}

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# include <vector>
# define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;

const int N=2003;
int n,m,color
;
vector<int> map
;
bool vis
;

bool dfs(int s){
    vis[s]=true;
    int len=map[s].size();
    for(int i=0;i<len;i++){
        int des=map[s][i];
        if(color[des]==color[s]) return false;
        if(color[des]==-1){
            color[des]=color[s]==0?1:0;
            if(!dfs(des)) return false;
        }
    }
    return true;
}
int main(){
    freopen("1.txt","r",stdin);
    int T,k=1;
    scanf("%d",&T);
    while(T--){
        CLR(map,0);
        CLR(vis,0);CLR(color,-1);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            map[a].push_back(b);
            map[b].push_back(a);
        }
        printf("Scenario #%d:\n",k++);
        bool flag=false;
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                color[i]=1;
                if(!dfs(i)){
                    flag=true;
                    break;
                }
            }
        }
        if(flag) printf("Suspicious bugs found!\n\n");
        else printf("No suspicious bugs found!\n\n");
    }
    return 0;
}