전국시대 - 15809

//15809 - 전국시대
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, M;
 
struct DisjointSet
{
    vector<int> parent, rank, army;
 
    DisjointSet(int n) : parent(n), rank(n, 1), army(n)                                 
    {
        for(int i = 1; i<n; ++i)
            parent[i] = i;
    }
 
    void setArmy()
    {
        for(int i = 1; i<=N; ++i)
            cin >> army[i];
    }
 
    int find(int u)
    {
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
 
    void merge(int u, int v)
    {
        u = find(u); v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        army[v] += army[u];
        if(rank[u] == rank[v]) ++rank[v];
    }
 
    void fight(int u, int v)
    {
        u = find(u); v = find(v);
        if(army[u] > army[v])
        {
            army[u] -= army[v];
            army[v] = 0;
            parent[v] = u;
        }
        else if(army[u] < army[v])
        {
            army[v] -= army[u];
            army[u] = 0;
            parent[u] = v;
        }
        else
            army[u] = army[v] = 0;
    }
};
 
int main()
{
    cin >> N >> M;
    DisjointSet sets(N+1);
    sets.setArmy();
    int flag, u, v;
    for(int i = 0; i<M; ++i)
    {
        cin >> flag >> u >> v;
        if(flag == 1)
            sets.merge(u, v);
        else
            sets.fight(u, v);
    }
    vector<int> bucket;
    for(int i = 1; i<=N; ++i)
        if(i == sets.find(i) && sets.army[i])
            bucket.push_back(sets.army[i]);
    sort(bucket.begin(), bucket.end());
    cout << bucket.size() << "\n";
    for(int i = 0; i<bucket.size(); ++i)
        cout << bucket[i] << " ";
}

 

 

 

 

 

 

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

15809번: 전국시대

 

 

 

 

 

 

전국 시대

union-find 문제입니다. 문제의 조건에 맞게 약간의 변형을 해주면 됩니다!