1.社交网络
https://www.acwing.com/problem/content/1599/
在一些社交网络平台上注册账号时，平台总是会要求你填写自己的兴趣爱好，以便找到一些具有相同兴趣爱好的潜在朋友。
社会集群是指一群有共同爱好的人。
给定社交网络中所有人的兴趣爱好，请你找到所有社会群集。
输入格式
第一行包含一个正整数 N，表示社交网络的人数。
所有人的编号为 1∼N。
接下来 N 行，每行包含一个人的爱好信息，格式如下：
Ki: hi[1] hi[2] … hi[Ki]
Ki 表示爱好数量，hi[j] 表示第 j 个爱好的编号。
输出格式
第一行输出总集群数量。
第二行按非递增顺序输出每个集群的人数。
数字之间空格隔开，行尾不得有多余空格。
数据范围
1≤N≤1000,
Ki>0,
爱好种类最多 1000 种，编号范围 [1,1000]。
输入样例：
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
输出样例：
3
4 3 1
(代码是仿照别的大佬题解写的)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1001;
int p[N],cnt[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
int n;
vector<int> hobby[N];//对应每一个兴趣爱好
scanf("%d",&n);
for(int i=0;i<=n;i++) p[i]=i;
for(int i=1;i<=n;i++)
{
int m,x;
scanf("%d:",&m);
while(m--)
{
scanf("%d",&x);
hobby[x].push_back(i);//第i人的兴趣爱好有x
}
}
for(int i=1;i<=1000;i++)
{
for(int j=0;j<hobby[i].size();j++)
{
int first=hobby[i][0];//将每个兴趣的第一个人与该兴趣中的其他人相连
int u=hobby[i][j];
first=find(first);
u=find(u);
if(u!=first)
{
p[u]=first;
}
}
}
for(int i=1;i<=n;i++)
{
cnt[find(i)]++;//第i个人属于find(i)这个圈子，这个圈子人数加一
}
sort(cnt,cnt+n+1,greater<int>());//从大到小排序
int k=0;
while(cnt[k]) k++;
printf("%d\n",k);//有k个圈子
for(int i=0;i<k;i++)
{
if(i!=0) printf(" ");
printf("%d",cnt[i]);
}
}
2.红色警报
https://pintia.cn/problem-sets/994805046380707840/problems/994805063963230208
L2-013 红色警报 (25 分)
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。
输入格式：
输入在第一行给出两个整数N（0 < N ≤ 500）和M（≤ 5000），分别为城市个数（于是默认城市从0到N-1编号）和连接两城市的通路条数。随后M行，每行给出一条通路所连接的两个城市的编号，其间以1个空格分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。
注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。
输出格式：
对每个被攻占的城市，如果它会改变整个国家的连通性，则输出Red Alert: City k is lost!，其中k是该城市的编号；否则只输出City k is lost.即可。如果该国失去了最后一个城市，则增加一行输出Game Over.。
输入样例：
5 4
0 1
1 3
3 0
0 4
5
1 2 0 4 3
结尾无空行
输出样例：
City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
Game Over.
结尾无空行
思路：把每两个城市之间的连接看成一条条边用结构体存储，用一个数组vis存储某个城市是否被攻陷
把开始状态时的连通块数量记录一下，然后每输入一个被攻陷的城市就计算一次连通块数量，若连通块数量加一或者不变，则说明被攻陷的城市不影响连通性，（攻陷表现为vis[x]==1）。
#include<iostream>
using namespace std;
const int N=10010;
int p[N],vis[N];
struct edge{//存储每条边的信息
int a;
int b;
};
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
int n,m;
edge e[N];
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) p[i]=i;
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
e[i].a=a;
e[i].b=b;
a=find(a);
b=find(b);
if(a!=b)
p[a]=b;
}
int sum1=0,sum2=0;//sum1代表前一次的连通块的数量，sum2代表后一次的数量
for(int i=0;i<n;i++)
{
if(p[i]==i) sum1++;
}
int k;
scanf("%d",&k);
for(int j=0;j<k;j++)
{
int x;
scanf("%d",&x);
sum2=0;
vis[x]=1;//vis数组赋1代表该地已被攻陷
for(int i=0;i<n;i++) p[i]=i;
for(int i=0;i<m;i++)
{
if(vis[e[i].a]||vis[e[i].b]) continue;//该边的某个点被攻陷，则代表这条边不再存在
p[find(e[i].a)]=find(e[i].b);//若两个点都还在就连接
}
for(int i=0;i<n;i++)
{
if(p[i]==i) sum2++;
}
if(sum2-1==sum1||sum2==sum1) printf("City %d is lost.\n",x);
else printf("Red Alert: City %d is lost!\n",x);
sum1=sum2;
}
if(k>=n) printf("Game Over.");
}
3.部落
https://pintia.cn/problem-sets/994805046380707840/problems/994805056736444416
L2-024 部落 (25 分)
在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。
输入格式：
输入在第一行给出一个正整数N（≤10
4
），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：
K P[1] P[2] ⋯ P[K]
其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过10
4
。
之后一行给出一个非负整数Q（≤10
4
），是查询次数。随后Q行，每行给出一对被查询的人的编号。
输出格式：
首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。
输入样例：
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7
结尾无空行
输出样例：
10 2
Y
N
结尾无空行
#include<iostream>
using namespace std;
const int N=100010;
int p[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
int n;
int max=-1;
scanf("%d",&n);
for(int i=1;i<=10010;i++) p[i]=i;
while(n--)
{
int m;
scanf("%d",&m);
int first;
for(int i=0;i<m;i++)
{
int x;
scanf("%d",&x);
if(i==0) first=x;
if(x>max) max=x;
p[find(x)]=find(first);
}
}
int sum=0;
for(int i=1;i<=max;i++) if(p[i]==i) sum++;
printf("%d %d\n",max,sum);
int k;
scanf("%d",&k);
while(k--)
{
int a,b;
scanf("%d%d",&a,&b);
if(find(a)==find(b)) printf("Y\n");
else printf("N\n");
}
}
