Social Clusters
社会集群是指一群有共同爱好的人。
给定社交网络中所有人的兴趣爱好，请你找到所有社会群集。
数据范围
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
样例解释
共 3 个集群：
4 人集群 {2,4,6,8}，他们都有共同的爱好 4。
3 人集群 {3,5,7}，其中 3 和 5 有共同的爱好 3，3 和 7 有共同的爱好 5。
1 人集群 {1}
思路
因为这里是具有相同爱好的人合并，主体是人，所以应存储的是每爱好对应的人的编号，再遍历每一个爱好，合并其中的人
import java.util.*;
import java.math.*;
import java.io.*;
public class Main{
static class Solution {
int N=1005, fa[];
List<Integer> g[];
int find(int u) {
if (fa[u]==u)
return u;
return fa[u]=find(fa[u]);
}
void merge(int u, int v) {
int fu=find(u), fv=find(v);
if (fu!=fv) {
fa[fu]=fv;
}
}
void init() {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n=sc.nextInt();
g=new ArrayList[N]; fa=new int[N];
for (int i=1; i<N; i++) {g[i]=new ArrayList<>(); fa[i]=i;}
sc.nextLine();
for (int i=1; i<=n; i++) {
String[] line = sc.nextLine().split(" ");
for (int j=1; j<line.length; j++) {
g[Integer.parseInt(line[j])].add(i);
}
}
for (int i=1; i<N; i++)
for (int j=1; j<g[i].size(); j++) {
merge(g[i].get(0), g[i].get(j));
}
int cnt[]=new int[N], c=0;
for (int i=1; i<=n; i++) {
cnt[find(i)]++;
}
List<Integer> ans = new ArrayList<>();
for (int i=1; i<=n; i++) if (cnt[i]!=0) {
ans.add(cnt[i]);
c++;
}
Collections.sort(ans, (e1, e2) -> {
return e2-e1;
});
System.out.println(c);
System.out.print(ans.get(0));
for (int i=1; i<ans.size(); i++) {
System.out.print(" "+ans.get(i));
}
}
}
public static void main(String[] args) throws IOException {
Solution s = new Solution();
s.init();
}
}
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int fa[N];
vector<int> v[N];
int find(int u) {
return fa[u]==u ? u : fa[u]=find(fa[u]);
}
void merge(int u, int v) {
int fu=find(u), fv=find(v);
if (fu!=fv) {
fa[fu]=fv;
}
}
int main() {
int n; scanf("%d", &n);
for (int i=1; i<N; i++) fa[i]=i;
for (int i=1; i<=n; i++) {
int k, h; scanf("%d: ", &k);
for (int j=0; j<k; j++) scanf("%d", &h), v[h].push_back(i);
}
for (int i=1; i<N; i++)
for (int j=1; j<v[i].size(); j++) {
merge(v[i][0], v[i][j]);
}
vector<int> ans;
int cycle=0, cnt[N]; memset(cnt, 0, sizeof cnt);
for (int i=1; i<=n; i++) cnt[find(i)]++;
for (int i=1; i<=n; i++) if (cnt[i]>0) {
ans.push_back(cnt[i]);
cycle++;
}
printf("%d\n", cycle);
sort(ans.begin(), ans.end(), [&](int a, int b) {return a>b;});
for (int i=0; i<ans.size(); i++) {
if (i==ans.size()-1) printf("%d", ans[i]);
else printf("%d ", ans[i]);
}
return 0;
}
Family Property
需要知道每个家庭的成员数，以及人均不动产面积和人均房产套数。
输入
ID Father Mother k Child_1 ... child_k M_estate Area
其中 ID 是每个人的独一无二的 4 位数标识号，Father 和 Mother 是这个人的父母的 ID 号（父母去世则用 -1 代替），k 是孩子数量，Child_i 是孩子的 ID，M_estate 是其名下房产数量，Area 是其名下房产的总面积。
输出
ID M AVG_sets AVG_area
其中 ID 是家庭成员中编号最小的成员编号，M 是家庭成员数，AVG_sets 是人均房产套数，AVG_area 是人均房产面积。
思路
定义person结构体存储每个人的id、fID，mID，children，房产等信息；
定义family结构体存每个家庭（存储输出的答案）的id、平均房产、平均房产数量等信息
让merge的逻辑修改为编号较小的为根
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int fa[N], vis[N];
struct person{
int id, fID, mID, childs[10], num, area;
} P[N];
struct family {
int id, tot, is_root;
double avg_num, avg_area;
} ans[N];
int find(int u) {
return fa[u]==u ? u : fa[u]=find(fa[u]);
}
void merge(int u, int v) {
int fu=find(u), fv=find(v);
if (fu==fv) return;
if (fu>fv) fa[fu]=fv;
else fa[fv]=fu;
}
bool cmp(family& a, family& b) {
if (a.avg_area!=b.avg_area) return a.avg_area>b.avg_area;
return a.id<b.id;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin>>n;
for (int i=0; i<N; i++) fa[i]=i;
for (int i=0; i<n; i++) {
int k; cin>>P[i].id>>P[i].fID>>P[i].mID>>k;
vis[P[i].id]=1;
if (P[i].fID!=-1) merge(P[i].id, P[i].fID), vis[P[i].fID]=1;
if (P[i].mID!=-1) merge(P[i].id, P[i].mID), vis[P[i].mID]=1;
for (int j=0; j<k; j++) cin>>P[i].childs[j], merge(P[i].id, P[i].childs[j]), vis[P[i].childs[j]]=1;
cin>>P[i].num>>P[i].area;
}
for (int i=0; i<n; i++) {
int rt=find(P[i].id); //找到这个人的根
ans[rt].id=rt;
ans[rt].avg_num+=P[i].num;
ans[rt].avg_area+=P[i].area;
ans[rt].is_root=1;
}
int familys=0;
for (int i=0; i<N; i++) {
int rt=find(i);
if (vis[rt]) ans[rt].tot++;
}
for (int i=0; i<N; i++) if (ans[i].is_root) {
familys++;
ans[i].avg_num=1.0*ans[i].avg_num/ans[i].tot;
ans[i].avg_area=1.0*ans[i].avg_area/ans[i].tot;
}
sort(ans, ans+N, cmp);
printf("%d\n", familys);
for (int i=0; i<N; i++) if (ans[i].is_root) {
printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].tot, ans[i].avg_num, ans[i].avg_area);
}
return 0;
}
Birds in Forest
假设所有出现在同一张照片中的鸟都属于同一棵树。
请你帮助科学家计算森林中树木的最大数量，对于任何一对鸟类，请判断它们是否在同一棵树上。
思路
有一个点没过，直觉告诉我可能是最大的鸟的个数那里不对，可仔细想想，他问可能诶，不就是最大鸟的编号吗，改了下代码就a了；
讲下我的思路：我用sz数组存储每棵树的大小，初始为1，当发生合并时，主树的大小加上被合并的树的大小，被合并的树清空（即将其sz设置为0）
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int fa[N], sz[N];
int find(int u) {
return fa[u]==u ? u : fa[u]=find(fa[u]);
}
void merge(int u, int v) {
int fu=find(u), fv=find(v);
if (fu!=fv) {
fa[fv]=fu;
sz[fu]+=sz[fv];
sz[fv]=0;
}
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, maxB=0; cin>>n;
for (int i=1; i<N; i++) fa[i]=i, sz[i]=1;
for (int i=0; i<n; i++) {
int k; cin>>k;
int b[k]; for (int j=0; j<k; j++) cin>>b[j], maxB=max(maxB, b[j]);
for (int j=1; j<k; j++) merge(b[0], b[j]);
}
int trees=0;
for (int i=1; i<=maxB; i++) if (sz[i]) {
trees++;
}
cout << trees << ' ' << maxB << '\n';
int Q; cin>>Q;
while (Q--) {
int u,v; cin>>u>>v;
cout<<(find(u)==find(v) ? "Yes" : "No") << '\n';
}
return 0;
}