제국 - 16402

//16402 - 제국
 
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
 
int N, M;
vector<string> name;
map<string, int> m;
 
struct DisjointSet
{
    vector<int> parent;
 
    DisjointSet(int n) : parent(n)
    {
        for(int i = 0; i<n; ++i)
            parent[i] = i;
    }
 
    int find(int u)
    {
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
 
    void merge(int u, int v)
    {
        if(u == find(v))
            return;
        else if(find(u) == v)
        {
            parent[u] = u;
            parent[v] = u;
            return;
        }
 
        u = find(u);
        v = find(v);
        parent[v] = u;
    }
};
 
void init()
{
    cin >> N >> M;
    name = vector<string>(N);
    m = map<string, int>();\
    getline(cin, name[0]);
    for(int i = 0; i<N; ++i)
    {
        getline(cin, name[i]);
        m[name[i]] = i;
    }
    DisjointSet set(N);
    string s1, s2;
    char c;
    for(int i = 0; i<M; ++i)
    {
        s1.clear(); s2.clear();
        while(true)
        {
            scanf("%c", &c);
            if(c == ',')
                break;
            s1 += c;
        }
        while(true)
        {
            scanf("%c", &c);
            if(c == ',')
                break;
            s2 += c;
        }
        cin >> c;
        if(c == '1')
            set.merge(m[s1], m[s2]);
        else
            set.merge(m[s2], m[s1]);
        scanf("%c", &c);
    }
    vector<string> ans;
    for(int i = 0; i<N; ++i)
        if(set.parent[i] == i)
            ans.push_back(name[i]);
    cout << ans.size()<< "\n";
    sort(ans.begin(), ans.end());
    for(int i = 0; i<ans.size(); ++i)
        cout <<  ans[i] << "\n";
}
 
int main()
{
    init();
}

 

 

 

 

 

 

https://www.acmicpc.net/problem/16402

16402번: 제국

 

 

 

 

 

 

제국

union-find 문제, 문제 조건에 맞게 merge()를 변형시켜주면 됩니다!