P2078 朋友

admin

题目背景
小明在A公司工作，小红在B公司工作。
https://www.luogu.org/problemnew/show/P2078


题目描述
这两个公司的员工有一个特点：一个公司的员工都是同性。

A公司有N名员工，其中有P对朋友关系。B公司有M名员工，其中有Q对朋友关系。朋友的朋友一定还是朋友。

每对朋友关系用两个整数(Xi,Yi)组成，表示朋友的编号分别为Xi，Yi。男人的编号是正数，女人的编号是负数。小明的编号是1，小红的编号是-1.

大家都知道，小明和小红是朋友，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）

输入输出格式
输入格式：
第1行，4个空格隔开的正整数N,M,P,Q。

之后P行，每行两个正整数Xi，Yi。

之后Q行，每行两个负整数Xi，Yi。

输出格式：
一行，一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）

输入输出样例
输入样例#1：
4 3 4 2
1 1
1 2
2 3
1 3
-1 -2
-3 -3
输出样例#1：
2
说明
对于30%数据，N,M<=100，P,Q<=200

对于80%数据，N,M<=4000,P,Q<=10000.

对于全部数据，N,M<=10000,P,Q<=20000。

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int fa[55000],p,q,x,y,n,m,all1=0,all2=0;
    
14. int getf(int u)
    
15. {
    
16.         if(fa[u]==u)
    
17.                 return u;
    
18.         int temp=getf(fa[u]);
    
19.         fa[u]=temp;
    
20.         return temp;
    
21. }
    
22. int main()
    
23. {  
    
24.         scanf("%d%d%d%d",&n,&m,&p,&q);
    
25.         for(int i=1;i<=n+m;i++)
    
26.                 fa[i]=i;
    
27.         for(int i=1;i<=p;i++)
    
28.         {
    
29.                 scanf("%d%d",&x,&y);
    
30.                 int t1=getf(x),t2=getf(y);
    
31.                 if(t1!=t2)
    
32.                         fa[t1]=t2;
    
33.         }
    
34.         for(int i=1;i<=q;i++)
    
35.         {
    
36.                 scanf("%d%d",&x,&y);
    
37.                 int t1=getf(n-x),t2=getf(n-y);
    
38.                 if(t1!=t2)
    
39.                         fa[t1]=t2;
    
40.         }
    
41.         for(int i=1;i<=n;i++)
    
42.                 if(getf(i)==getf(1))
    
43.                         all1++;
    
44.         for(int i=n+1;i<=n+m;i++)
    
45.                 if(getf(i)==getf(n+1))
    
46.                         all2++;
    
47.         printf("%d",min(all1,all2));
    
48.     return 0;
    
49. }

复制代码

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int n,m,p,q,ans1,ans2;
   
4. int par[20001];
   
5. int f(int a)
   
6. {
   
7.     while(par[a]!=par[par[a]])par[a]=par[par[a]];
   
8.     return par[a];
   
9. }
   
10. void merge(int a,int b)
    
11. {
    
12.     int r1=f(a);
    
13.     int r2=f(b);
    
14.     if(r1==r2)return;
    
15.     else par[r1]=r2;
    
16. }
    
17. int main()
    
18. {
    
19.     cin>>n>>m>>p>>q;
    
20.     for(int i=1;i<=n+m;i++)par[i]=i;
    
21.     int x,y;
    
22.     for(int i=1;i<=p;i++)
    
23.     {
    
24.         cin>>x>>y;
    
25.         merge(x,y);
    
26.     }
    
27.     for(int i=1;i<=q;i++)
    
28.     {
    
29.         cin>>x>>y;
    
30.         merge(-x+n,-y+n);
    
31.     }
    
32.      for(int i=1;i<=n;++i)
    
33.      if(f(i)==f(1))
    
34.       ans1++;
    
35.     for(int i=n+1;i<=n+m;++i)
    
36.      if(f(i)==f(n+1))
    
37.       ans2++;
    
38.     cout<<min(ans1,ans2);
    
39.     return 0;
    
40. }
    

复制代码

walk_alone

1. #include <cstdio>
   
2. #include <algorithm>
   
3. #include <map>
   
4. using namespace std;
   
5. map<int,int> father;
   
6. int getfather(int x)
   
7. {
   
8.         if(x==father[x])
   
9.                 return x;
   
10.         return father[x]=getfather(father[x]);
    
11. }
    
12. int main()
    
13. {
    
14.         int n,m,p,q,a,b,sum1=0,sum2=0;
    
15.     scanf("%d%d%d%d",&n,&m,&p,&q);
    
16.     for(int i=-m;i<=n;i++)
    
17.                 father[i]=i;
    
18.     for(int i=1;i<=p+q;i++)
    
19.         {
    
20.         scanf("%d%d",&a,&b);
    
21.         father[getfather(a)]=getfather(b);
    
22.         }
    
23.     for(int i=-m;i<=-1;i++)
    
24.                 if(getfather(i)==getfather(-1))
    
25.                         sum1++;
    
26.     for(int i=1;i<=n;i++)
    
27.                 if(getfather(i)==getfather(1))
    
28.                         sum2++;
    
29.     printf("%d",min(sum1,sum2));
    
30. }

复制代码

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. int n,m,p,q;
   
4. const int mx=10010;
   
5. int par[mx][3],i;///par[mx][1]是男
   
6. int getpar(int a,int x)
   
7. {
   
8.     ///找根节点
   
9.     if (par[a][x]!=a)
   
10.         par[a][x]=getpar(par[a][x],x);
    
11.     return par[a][x];
    
12. }
    
13. void merge_(int a,int b,int x)
    
14. {
    
15.     ///合并a，b所在集合
    
16.     par[getpar(a,x)][x]=getpar(b,x);
    
17.     return;
    
18. }
    
19. int main()
    
20. {
    
21.     cin>>n>>m>>p>>q;
    
22.     for (i=1; i<=n; i++) par[i][1]=i;
    
23.     for (i=1; i<=m; i++) par[i][2]=i;
    
24.     for (i=1; i<=p; i++)
    
25.     {
    
26.         int a,b;
    
27.         cin>>a>>b;
    
28.         merge_(a,b,1);
    
29.     }
    
30.     for (i=1; i<=q; i++)
    
31.     {
    
32.         int a,b;
    
33.         cin>>a>>b;
    
34.         a=-a,b=-b;
    
35.         merge_(a,b,2);
    
36.     }
    
37.     int ansa=0,ansb=0;
    
38.     for (i=1; i<=n; i++)
    
39.         if (getpar(i,1)==getpar(1,1)) ansa++;
    
40.     for (i=1; i<=m; i++)
    
41.         if (getpar(i,2)==getpar(1,2)) ansb++;
    
42.     cout<<min(ansa,ansb);
    
43.     return 0;
    
44. }
    

复制代码