当前位置: 代码迷 >> 综合 >> uva1160 X-Plosives
  详细解决方案

uva1160 X-Plosives

热度:98   发布时间:2023-12-07 01:33:09.0

UVA 1160 X-Plosives

 

题意:

        现在手上有一些化合物,每个化合物都不相同且由两个不同整数构成,当你手上存在这种情况时:

        手上有至少N(N>2)个化合物且其中有N个化合物正好包含N个不同的整数(即这N个整数每个出现了2次)。那么此时化合物不稳定。比如你有化合物(1,2),(2,3),(3,1)那么就是不稳定的,但是你如果只有(1,2),(2,3) 那么就是稳定的。

        现在给出所有化合物给你的顺序,你要保证不会出现化合物不稳定的情况,输出你需要拒绝化合物的个数。

        输入:包含多组实例。每个实例由连续的一对整数构成(整数属于[0,10^5])。不同实例之间是一个空行,没有重复的化合物会出现,且单行-1表示当前实例的输入结束。

        输出:输出你需要拒绝的化合物个数。

分析:

        把每个整数看成是节点,对应的化合物看成对应的边,那么就形成了一个无向图。

        图中有环  充要条件  化合物不稳定

        我们添加某个化合物会不稳定  充要条件是  该化合物的两种元素已经属于同一个连通分量了

        判断化合物的两种元素已经在同一个连通分量时,直接拒绝即可。

        本题需小心处理输入数据的输入格式。

 

 

 

#include<cstdio>

#include<cstring>

using namespace std;

#define maxn 500005

int pre[maxn];

int Find(int m)

{

    int n=m;

    while(n!=pre[n])

        n=pre[n];

    return n;

}

void Merge(int x,int y)

{

    int fx=Find(x);

    int fy=Find(y);

    if(fx<fy)

        pre[fy]=fx;//大的指向小的

    else

        pre[fx]=fy;

}

void init()

{

    int i;

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

        pre[i]=i;

}

int main()

{

    int x,y;

    while(scanf("%d",&x)==1)

    {

        if(x==-1)//特例

        {

            printf("0\n");

            continue;

        }

        int cnt=0;//需要拒绝的化合物数

        init();

        while(x!=-1)

        {

            scanf("%d",&y);

            if(Find(x) == Find(y))

                ++cnt;

            else

                Merge(x,y);

            scanf("%d",&x);

        }

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

    }

    return 0;

}