首页 > 其他 > 详细

L3-003. 社交集群

时间:2018-03-07 17:54:45      阅读:160      评论:0      收藏:0      [点我收藏+]

并查集,方法很多,提供一个简单的思路。

(多找找一一对应的关系)

代码:

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int fa[1010];
vector<int> mp[1010];
int vis[1010];
void init()
{
   for(int i=1;i<=1000;i++) fa[i]=i,vis[i]=0;
}
int Find(int x)
{
    int temp=x;
    while(temp!=fa[temp]) temp=fa[temp];
    return temp;
}
void Merge(int x,int y)
{
    int xx=Find(x);
    int yy=Find(y);
    if(xx!=yy) fa[xx]=yy;
}
bool cmp(int x,int y)
{
    return x>=y;
}
int main()
{
    int n;
    cin>>n;
    init();
    for(int Case=1;Case<=n;Case++)
    {
        int k;
        scanf("%d:",&k);
        int pre;
        for(int i=1;i<=k;i++)
        {
            int x;
            scanf("%d",&x);
            vis[x]=1;
            mp[x].push_back(Case);// id
            if(i!=1) Merge(pre,x);
            pre=x;
        }
    }
    vector<int> res;
    for(int i=1;i<=1000;i++) if(vis[i]==1 && fa[i]==i)
        res.push_back(i);
    int len=res.size();
    cout<<len<<endl;

    int a[1010];
    int alen=0;
    for(int i=0;i<len;i++)
    {
        set<int> s;//
        for(int j=1;j<=1000;j++)
        {
            if(vis[j]==1 && fa[j]==res[i])
            {
                int mplen=mp[j].size();
                for(int zz=0;zz<mplen;zz++) s.insert(mp[j][zz]);
            }
        }
        a[alen++]=s.size();
    }
    sort(a,a+alen,cmp);
    for(int i=0;i<alen;i++)
    {
        if(i==0) printf("%d",a[i]);
        else printf(" %d",a[i]);
    }
    cout<<endl;
    return 0;
}

 

L3-003. 社交集群

原文:https://www.cnblogs.com/z1141000271/p/8523708.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!