UVA1160 X-Plosives

思路

每个元素设为点，化合物设为边

不能出现k条边k个点的环

直接并查集检查即可

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int fa[100100],ans=0,a,b;

void init(void){

    ans=0;

    for(int i=1;i<=100010;i++)

        fa[i]=i;

}

int find(int x){

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

}

void merge(int x,int y){

    if(find(x)==find(y))

        ans++;

    else

        fa[find(x)]=find(y);

}

int main(){

    freopen("test.in","r",stdin);

    freopen("test.out","w",stdout);

    while(scanf("%d",&a)==1){

        init();

        while(a!=-1){

            scanf("%d",&b);

            merge(a,b);

            scanf("%d",&a);

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

UVA1160 X-Plosives

思路

代码

最新文章

热门文章