【题解】P2078 朋友-C++

题目传送门
这道题目就是一个模板并查集
但是！唯一不同的地方在于，这道题的编号有负数。
C++的map你忘了吗！！！下表可以是任意类型。
所以把fa数组开成一个int->int的map就可以了
代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,z,x,y,m,b,q;
 4 map<int,int>fa;
 5 void init()
 6 {
 7       for(int i=-1*m;i<=n;i++)
 8       {
 9         fa[i]=i;
10     }
11 }
12 int get(int x)
13 {
14       if(fa[x]==x)
15           return x;
16       int r=get(fa[x]);
17       fa[x]=r;
18       return r;
19 }
20 void merge(int x,int y)
21 {
22       int r1=get(x);
23     int r2=get(y);
24     if(r1==r2)
25         return;
26     fa[r1]=r2;
27 }
28 int main()
29 {
30     cin>>n>>m>>b>>q;
31     init();
32     merge(1,-1);
33     for(int i=1;i<=b+q;i++)
34     {
35         cin>>x>>y;
36         merge(x,y);
37     }
38     int ans=0,an=0;
39     for(int i=1;i<=n;i++)
40     {
41         if(get(1)==get(fa[i]))ans++;
42     }
43     for(int i=-1*m;i<0;i++)
44     {
45         if(get(-1)==get(fa[i]))an++;
46     }
47     cout<<min(ans,an)<<endl;
48     return 0;
49 }

ov.

个人博客地址: www.moyujiang.com 或 moyujiang.top