LA3644简单并查集判环

题意:
      有n个化合物,每个化合物是两种元素组成,现在要装车,但是一旦车上的化合物中的某几个化合物组成这样一组关系,有n个化合物正好用了n中元素,那么就会爆炸,输入的顺序是装车的顺序,对于每个化合物只要他装上去会爆炸,那么就不能装他(不要考虑成最优什么的,题意的意思是直接模拟),问有多少个化合物不能装车?


思路:
      a个化合物正好由a中元素组成只有一种可能,那就是形成了环,那么每个化合物是两个元素组成就相当于是一条边,然后每加入一条边就判断这条边加入后会不会形成环,这个可以用并查集来简单判断,其他的没啥。


#include<stdio.h>


#define N 110000


int mer[N];


int finds(int x)
{
   return x == mer[x] ? x : mer[x] = finds(mer[x]);    
}


int main ()
{
   int x ,y ,Ans;
   while(~scanf("%d" ,&x))
   {
       for(int i = 0 ;i <= 100000 ;i ++)
       mer[i] = i;
       Ans = 0;
       while(x != -1)
       {
          scanf("%d" ,&y);
          x = finds(x);
          y = finds(y);
          if(x == y) Ans ++;
          else mer[x] = y;
          scanf("%d" ,&x);
       }                
       printf("%d " ,Ans);  
   }
   return 0;     
}





原文地址:https://www.cnblogs.com/csnd/p/12062561.html