题目描述

在一些社交网络平台上注册账号时，平台总是会要求你填写自己的兴趣爱好，以便找到一些具有相同兴趣爱好的潜在朋友。

社会集群是指一群有共同爱好的人。

给定社交网络中所有人的兴趣爱好，请你找到所有社会群集。
输入格式
第一行包含一个正整数 N，表示社交网络的人数。

所有人的编号为 1∼N。

接下来 N 行，每行包含一个人的爱好信息，格式如下：

Ki: hi[1] hi[2] … hi[Ki]
Ki 表示爱好数量，hi[j] 表示第 j 个爱好的编号。

输出格式
第一行输出总集群数量。

第二行按非递增顺序输出每个集群的人数。

数字之间空格隔开，行尾不得有多余空格。

数据范围
1≤N≤1000,
Ki>0,
爱好种类最多 1000 种，编号范围 [1,1000]。

说白了，就是通过 人-> 爱好 -> 人 -> …… -> 人的一个过程
可以假定给的数据是个图，当然和传统的图不太一样
我这里假定，行->人，列->爱好
即 f[i][j] 对应的i个人,j个爱好
所以很简单 使用一个dfs就可以找到集群了(BFS也可以)

样例

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

算法1 DFS

空间复杂度

$O(n^2)$

时间复杂度

$O(n^2)$

C++ 代码

#include<string>
#include<math.h>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<map>
#include<iostream>
#include<vector>
#include<climits>
#include<iomanip>
#include<set>

using namespace std;

const int MAXN =1010;

int n,k;
int graph[MAXN][MAXN]; 
int visit[MAXN]={0};

vector<int> ans;
int cnt= 0 ;
void DFS(int i , int & count ,int type){
    // about tpye: 1 is people, 0 is hobby
    if(type){
        // record the people had been visited
        visit[i] = 1;
        count++;
        // find all the people's hobby
        for(int j = 1; j <= cnt;j++ ){
            if(graph[i][j]){
//              cout<<"访问 "<<i<<" 人的hobby "<<j <<endl;
                DFS(j,count,0);
            }
        }
    }
    else{
        //find all people who have the i hobby;
        for(int j = 1; j <= n ;j++){
            if(graph[j][i] && visit[j] != 1){
//              cout<<"访问 "<<i<<" hobby的人 "<<j <<endl;
                DFS(j,count,1);
            }
        }
    } 

}

int main(){
    scanf("%d",&n);
    for(int i = 1 ; i  <= n ;  i++){
        scanf("%d:",&k);
        for(int j = 0 ; j < k; j++){
            int hobby;
            scanf("%d",&hobby);
            cnt = max(cnt,hobby);
            graph[i][hobby] =1;
        }
    }

    for(int i = 1; i <= n; i++ ){
        if(visit[i] != 1){
            int count= 0;
            DFS(i,count,1);
            ans.push_back(count);
        }
    }
    sort(ans.begin(),ans.end(),greater<int>());
    cout<<ans.size()<<endl;
    cout<<ans[0];
    for(int i = 1; i < ans.size();i++){
        cout<<" "<<ans[i];
    }

}