當你在社交網(wǎng)絡(luò)平臺注冊時，一般總是被要求填寫你的個人興趣愛好，以便找到具有相同興趣愛好的潛在的朋友。一個“社交集群”是指部分興趣愛好相同的人的集合。你需要找出所有的社交集群。

輸入格式

輸入在第一行給出一個正整數(shù) N（≤1000），為社交網(wǎng)絡(luò)平臺注冊的所有用戶的人數(shù)。于是這些人從 1 到 N 編號。隨后 N 行，每行按以下格式給出一個人的興趣愛好列表：$K_i:h_i[1]h_i[2]...h_i[K_i]$，其中 $K_i(>0)$ 是第 i 個人的興趣愛好的個數(shù)，$h_i[j]$是第$j$個興趣愛好的編號。為區(qū)間[1, 1000]內(nèi)的整數(shù)。

輸出格式

首先在一行中輸出不同的社交集群的個數(shù)。隨后第二行按非增序輸出每個集群中的人數(shù)。數(shù)字間以一個空格分隔，行末不得有多余空格。

輸入樣例

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

一些限制

項目	限制
代碼長度限制	16 KB
時間限制	3000 ms
內(nèi)存限制	64 MB
棧限制	8192 KB

解題思路

因為每一個人的興趣愛好不止一個，如果我們按照單一的興趣愛好來合并，那就會非常不妥當（當然，這樣做也是可以通過的，但所花的時間會更多）。

我們可以這樣做：

1. 先設(shè)置一個映射關(guān)系unordered_map<int, vector<int>>，將每個人歸入到每個興趣愛好的集合中。
2. 遍歷這個映射關(guān)系，對于每一個興趣愛好的集合，將這個集合中的人合并到一個朋友圈中。

   for(auto k: lov) {for(int i = 0, j = 1; j < k.second.size(); ++j) {union1(k.second[i], k.second[j]);}
   }
   

3. 最后，使用set容器來存儲所有的朋友圈，使用unordered_map來存儲每個朋友圈的人數(shù)，最后輸出結(jié)果。

   set<int> components;
   unordered_map<int, int> mp;
   for(int i = 1; i <= n; ++i) {components.insert(components.end(), fa[i]);if(mp.find(fa[i]) == mp.end()) mp[fa[i]] = 1;else mp[fa[i]] += 1;
   }
   cout << components.size() << endl;
   vector<int> ans;
   for(auto i: mp) {ans.push_back(i.second);
   }
   

Code

#include <bits/stdc++.h>
using namespace std;
int fa[2000];
set<int> components;
unordered_map<int,vector<int>> lov;void init(int n) {for(int i = 1; i <= n; ++i) {fa[i] = i;}
}int find(int i) {if(i == fa[i]) return i;else {fa[i] = find(fa[i]);return fa[i];}
}int update(int i) {if(i == fa[i]) return i;else {fa[i] = find(fa[i]);return fa[i];}
}void union1(int a, int b) {int afa = find(a), bfa = find(b);fa[afa] = bfa;
}bool cmp(int a, int b) {return a > b;
}int main() {int n, m, t;cin >> n;init(n);for(int i = 1; i <= n; ++i) {scanf("%d: ", &m);for(int j = 1; j <= m; ++j) {scanf("%d", &t);lov[t].push_back(i);}}for(auto k: lov) {for(int i = 0, j = 1; j < k.second.size(); ++j) {union1(k.second[i], k.second[j]);}}for(int i = 0; i <= n; ++i) {update(i);}unordered_map<int, int> mp;for(int i = 1; i <= n; ++i) {components.insert(components.end(), fa[i]);if(mp.find(fa[i]) == mp.end()) mp[fa[i]] = 1;else mp[fa[i]] += 1;}cout << components.size() << endl;vector<int> ans;for(auto i: mp) {ans.push_back(i.second);}sort(ans.begin(), ans.end(), cmp);for(int i = 0; i < ans.size(); ++i) {if(i == 0) cout << ans[i];else cout << " " << ans[i];}
}