易爆物D305

分析：典型的并查集，每一个物品合一看成一个独立的顶点，则一个简单化合物就是一条边，如果两个顶点x,y联通则说明有危险，所以可以用一个并查集来维护图的联通分量集合，并查集的详解有一篇写的很易懂的博客并查集详解，看完之后觉得别具一格，推荐给正在学习并查集的ACER们。

并查集主要是由保存上级的数组pre[]，Find（）函数，Join（）函数进行实现，Find函数是用来查找元素的根节点，join函数用来连接两个节点，将联通分量合并为一个。

而在此题中，只需要使用Find函数查找两个元素x,y是否在同一个集合中，也就是时候构成了一种化合物， 并不用用到join函数进行合并。

上代码：

 #include <cstdio>

 #include <iostream>

 int pa[];

 int x,y,n;

 inline int read(){

     int f = , x = ;

     char ch;

     do{

         ch = getchar();

         if(ch == '-') f  = -;

     }

     while(ch < '' || ch > '');

     do{

         x = x *  + ch - '';

         ch = getchar();

     }

     while(ch <= '' && ch >= '');

     return x * f;

 }

 inline int Find(int x){

     return pa[x]!=x?pa[x] = Find(pa[x]):x;

 }

 int main(){

     n = read();

     for(int i = ; i <= ; i ++) pa[i] = i;

     int ans = ;

     while(n --){

        x = read();

        y = read();

        x = Find(x);

        y = Find(y);

        if(x == y) ans ++;

        else pa[x] = y;

     }

     printf("%d", ans);

     return ;

 }

代码快来拿！！！