Skip to content

L3-003 社交集群

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 1200 ms
  • 内存限制: 64 MB

当你在社交网络平台注册时，一般总是被要求填写你的个人兴趣爱好，以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。

输入格式

输入在第一行给出一个正整数 N（\le 1000），为社交网络平台注册的所有用户的人数。于是这些人从 1 到 N 编号。随后 N 行，每行按以下格式给出一个人的兴趣爱好列表：

K_i: h_i[1] h_i[2] … h_i[K_i]

其中K_i (>0)是兴趣爱好的个数，h_i[j]是第j个兴趣爱好的编号，为区间 [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

Tutorial

思路：

并查集

用一个 cou[i] 来表示第 i 门课程的第一个感兴趣的人。

合并的时候：

  • 判断 cou[i]
  • 如果 cou[i] 存在第一个感兴趣的人, 那么将这两人join起来
  • 如果不存在, 那么这门课程第一个感兴趣的人就是这个人
  • 最后找有几个连通块

Solution

#include <ctype.h>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define CLR(a) memset(a, 0, sizeof(a))

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const double PI = 3.14159265358979323846264338327;
const double E = exp(1);
const double eps = 1e-6;

const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
const int MOD = 1e9 + 7;

int pre[maxn], cou[maxn];

int find(int x) {
    int r = x;
    while (pre[r] != r) r = pre[r];
    int j = x, i;
    while (j != r) {
        i = pre[j];
        pre[j] = r;
        j = i;
    }
    return r;
}

void join(int x, int y) {
    int fx = find(x), fy = find(y);
    if (x != fy)
        pre[fx] = fy;
}

bool comp(int x, int y) {
    return x > y;
}

int main() {
    CLR(cou);
    int n, k, num;
    cin >> n;
    for (int i = 1; i <= n; i++) pre[i] = i;
    for (int i = 1; i <= n; i++) {
        scanf("%d:", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &num);
            if (cou[num])
                join(i, cou[num]);
            else
                cou[num] = i;
        }
    }
    map<int, int> m;
    for (int i = 1; i <= n; i++) m[find(i)]++;
    vector<int> v;
    map<int, int>::iterator it;
    for (it = m.begin(); it != m.end(); it++) v.push_back(it->second);
    sort(v.begin(), v.end(), comp);
    int len = v.size();
    cout << len << endl;
    for (int i = 0; i < len; i++) {
        if (i)
            printf(" ");
        printf("%d", v[i]);
    }
    cout << endl;
}
Last update: May 4, 2022
Back to top