易爆物D305

易爆物D305"/>

易爆物D305

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

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

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

上代码：

 1 #include <cstdio>
 2 #include <iostream>
 3 
 4 int pa[100010];
 5 int x,y,n;
 6 
 7 inline int read(){
 8     int f = 1, x = 0;
 9     char ch;
10     do{
11         ch = getchar();
12         if(ch == '-') f  = -1;
13     }
14     while(ch < '0' || ch > '9');
15     do{
16         x = x * 10 + ch - '0';
17         ch = getchar();
18     }
19     while(ch <= '9' && ch >= '0');
20     return x * f;
21 }
22 
23 inline int Find(int x){
24     return pa[x]!=x?pa[x] = Find(pa[x]):x;
25 }
26 
27 int main(){
28     n = read();
29     for(int i = 0; i <= 100010; i ++) pa[i] = i;   
30     int ans = 0;
31     while(n --){
32        x = read();
33        y = read();
34        x = Find(x);
35        y = Find(y);
36        if(x == y) ans ++;
37        else pa[x] = y;
38     }
39     printf("%d", ans);
40     return 0;
41 }

转载于:.html