hiho 171周 - 水题，并查集

题目描述：

输入
4

alice 2 alice@hihocoder.com alice@gmail.com

bob 1 bob@qq.com

alicebest 2 alice@gmail.com alice@qq.com

alice2016 1 alice@qq.com

输出
alice alicebest alice2016

bob

如上所示，每一行前面是用户名，后面是他的邮箱，如果两个人共用了一个邮箱说明他是同一组的。

输出分组后的结果。一组占一行。组间顺序和组内顺序保证和输入相同。

数据大小是：最多10000个人，每个人最多10个email

The first line contains an integer N, denoting the number of usernames. (1 < N ≤ 10000)

Each username may have 10 emails at most.

-----------------------------------------------------------------------------------------------------------------------------------------

看着简单，还有有些细节需要注意的，比如顺序的保证。

上来就想建图求联通分量，想了一下没必要：如果每组都有10个email，则需要建边10*9*1w=90w条边，太麻烦了

后来一想用并查集做既省空间又省时间，每组的email都merge到每组的第一个上。这样每组的第一个email的父亲就对应着一个分组。

#include <map>

#include <cmath>

#include <vector>

#include <string>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = * + ;

int father[N];

int find(int id){

    int fid = father[id];

    if(fid==id) return fid;

    return father[id]=find(fid);

}

void merge(int a,int b){

    int fa = find(a);

    int fb = find(b);

    if(fa==fb) return;

    father[fb] = fa;

}

struct USER_MAILID{

    char name[];

    int mailId;

};

USER_MAILID names[];

vector<string > output_list[];

map<int,int> father_ouputId;

int main(){

    for(int i=;i<N;i++) father[i]=i;

    map<string,int> mail_id_mapper;  int mailId = ;

    int n,cnt; cin>>n;

    char strbuf[]; int id_buf[];

    for(int id=;id<n;id++){

        scanf("%s%d",names[id].name,&cnt);

        for(int i=;i<cnt;i++){

           scanf("%s",strbuf);

           auto iter = mail_id_mapper.find(strbuf);

           if(iter==mail_id_mapper.end()){

              mail_id_mapper[strbuf] = (id_buf[i] = mailId++);

           }

           else{

              id_buf[i] = iter->second;

           }

        }

        names[id].mailId = id_buf[];

        for(int i=;i<cnt;i++) for(int j=i+;j<cnt;j++){

           merge(id_buf[i],id_buf[j]);

        }

    }

    int curId = ; int outputId = ;

    for(int id=;id<n;id++){

        int f = find(names[id].mailId);

        auto iter = father_ouputId.find(f);

        if(iter==father_ouputId.end()){

            father_ouputId[f] = curId = outputId++;

        }

        else curId = iter->second;

        output_list[curId].push_back(names[id].name);

    }

    for(int i=;i<outputId;i++){

        for(int j=;j<output_list[i].size();j++){

            printf("%s ",output_list[i][j].c_str());

        }puts("");

    }

    return ;

}

巴特西

hiho 171周 - 水题，并查集

最新文章

热门文章