A Bug's Life POJ - 2492 (种类或带权并查集)

这个题目的写法有很多，用二分图染色也可以写，思路很好想，这里我们用关于并查集的两种写法来做。

题目大意：输入x,y表示x和y交配，然后判断是否有同性恋。

1 带权并查集：

　　我们可以用边的权值来表示一种关系，比如说

我们可以设权值为1，假如A和B发生关系，B和C发生关系，那么C到A的距离就是2，如果A和C发生关系，那就会产生矛盾，因此A和C是同性。

所以如果x和y可以发生关系，首先x和y必须在一棵树上，并且x和y到跟的距离必须同为奇数或者同为偶数。

code:

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=+;

int fa[N],w[N];

int find(int x){

    if(x==fa[x]) return x;

    else {

        int c=find(fa[x]);

        w[fa[x]]%=;

        w[x]=(w[x]+w[fa[x]])%;

        return fa[x]=c;

    }

}

bool unite(int x,int y){

    int fx=find(x),fy=find(y);

    if(fx!=fy){

        fa[fx]=fy;

        w[fx]=(w[y]-w[x]+)%;

        return ;

    }

    else {

        return w[x]%==w[y]%;

    }

}

void solve(int time){

    int n,m;

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

    for(int i=;i<=n;i++){

        fa[i]=i;

        w[i]=;

    }

    int ans=;

    for(int i=;i<=m;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        if(ans) continue ;

        if(unite(x,y)){

            ans++;

        //    break;//注意这里不能直接break...wa了好几发，但是CF是可以的。。。

        }

    }

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

    if(ans) puts("Suspicious bugs found!\n");

    else puts("No suspicious bugs found!\n");

}

int main(){

    int t;cin>>t;

    for(int i=;i<=t;i++) solve(i);

    return ;

}

2 种类并查集：

　　如果用种类并查集来写，那这个题就相当于食物链那道题目的缩水版。。。

　　将每个元素分为两类，x和x+n，如果x和y可以发生关系，那么x和y不能是同类，也就是说x和y不能是一类,x+n和y+n不能是一类。

　　code:

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=+;

int fa[N+N];

int find(int x){

    return fa[x]==x? x:fa[x]=find(fa[x]);

}

int unite(int x,int y){

    int fx=find(x),fy=find(y);

    fa[fx]=fy;

}

bool same(int x,int y){

    return find(x)==find(y);

}

void solve(int time){

    int n,m;

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

    for(int i=;i<=n+n;i++) fa[i]=i;

    int ans=;

    for(int i=;i<=m;i++){

        int x,y;

        scanf("%d%d",&x,&y);

        x--;y--;

        if(ans) continue ;

        if(same(x,y)||same(x+n,y+n)){

            ans=;

//            if(ans) break;//注意这里不能直接break...wa了好几发，但是CF是可以的。。。

        }

        else {

            unite(x,y+n);unite(y,x+n);

        }

    }

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

    if(ans) puts("Suspicious bugs found!\n");

    else puts("No suspicious bugs found!\n");

}

int main(){

    int t;cin>>t;

    for(int i=;i<=t;i++) solve(i);

    return ;

}

巴特西

A Bug's Life POJ - 2492 (种类或带权并查集)

最新文章

热门文章