[트리] EDITORWARS 에디터 전쟁

1. 문제

 

 

이 문제는 여러 집합들을 세 집합으로 나누는 문제이다

 

- 아무것도 속해있지 않은 집합

- b집합과 대치되는 a집합

- a집합과 대치되는 b집합

 

m개의 댓글에서

두명의 정보가 주어진다.

 

두명의 정보는 ack -> 같은 편, dis -> 다른편

 

으로 주어지고

 

이를 통해 a와 b 집합으로 나누는 것이다.

 

그 후 a와 b의 모순이 생기면 모순이 생기는 댓글의 인덱스를

모순이 생기지 않으면

 

아무것도 속해있지 않은 집합의 크기와 a,b중 더 큰 집합의 크기를 더한 값을 반환하면

문제를 해결할 수 있다.

 

 

2. 상호 배타적 집합: 유니온-파인드 자료구조

 

ack a b 가 주어지면  a 와 b를 합친다.

 

    이때 a와 b가 대치되는 사람 r[a] r[b] 가 있다고 하자

 

    그러면 ack r[a] r[b] 또한 참이 되므로 합칠 수 있다.

 

dis a b 가 주어졌다고 하고 대치되는 사람 r[a] r[b]이 있다고 하자

그러면 

 

ack a r[b]

ack r[a] b 

 

이라는 것을 알 수 있고

 

    r[a] = b

    r[b] = a

 

가 된다.

 

 

이와 같이 어떠한 상태이면 합치는 자료구조가 필요하다는 것을 알 수 있으므로 

상호 배타적 집합을 이용하여 문제를 해결 할 수 있다

 

찾기를 통해 루트만을 비교,

합치기를 통해 같은편을 루트 하나로 표현

 

코드는 다음과 같다.

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <utility>
#include <string>
using namespace std;
 
struct UnionFindSet {
    vector<int> father;
    vector<int> rank;
 
    vector<int> size;
 
    vector<int> reverse;
    UnionFindSet(int n): father(n), rank(n, 1), size(n,1), reverse(n) {
        for(int i = 0; i < n; i++){
            father[i] = i;
            reverse[i] = -1;
        }
    }
    int find(int u) {
        if(u == -1) return -1;
        if(u == father[u]) return u;
        return father[u] = find(father[u]);
    }
    bool merge(int u, int v) {
        u = find(u); v = find(v);
        int ru = find(reverse[u]), rv = find(reverse[v]);
        if(u == v) return true;
 
        if(rank[u] > rank[v])
            swap(u,v);
        father[u] = v;
        reverse[v] = ru > rv ? ru: rv;
        size[v] += size[u];
        size[u] = 0;
        if(rank[v] == rank[u]) rank[v]++;        
    }
    bool dis(int u, int v) {
        u = find(u); v = find(v);
        int ru = find(reverse[u]), rv = find(reverse[v]);
 
        if(u == v) return false;
        if(ru != -1) merge(ru, v);
        if(rv != -1) merge(rv, u);
 
        u = find(u); v = find(v);
 
        reverse[u] = v;
        reverse[v] = u;
        
        return true;
    }
    bool ack(int u, int v) {
        u = find(u); v = find(v);
        int ru = find(reverse[u]), rv = find(reverse[v]);
 
        if(ru == v || rv == u) return false;
        if(ru != -1 && rv != -1) merge(ru, rv);
        merge(u, v);
        return true;
    }
    int calc() {
        int ret = 0;
        int vim = 0;
        int emacs = 0;
        bool travel[10000] = {false, };
        for(int i = 0; i < father.size(); i++)
        {
            int u = find(i);
            if(travel[u]) continue;
            if(reverse[u] == -1){
                ret += size[u];
            }
            if(reverse[u] != -1) {
                int v = find(reverse[u]);
                vim += size[u] > size[v] ? size[u] : size[v];
                emacs += size[u] < size[v] ? size[u] : size[v];
                travel[v] = true;
            }
            travel[u] = true;
        }
        return ret + vim;
 
    }
};
int C;
int N;
int M;
vector<pair<int, pair<int, int> > > comment;
 
void findContradiction() {
    UnionFindSet S(N);
    for(int i = 0 ; i < M; i++) {
        int u = comment[i].second.first;
        int v = comment[i].second.second;
        if(! (comment[i].first == 1 ? S.ack(u, v) : S.dis(u, v))) {
            cout<<"CONTRADICTION AT "<<i+1<<"\n";
            return;
        }
    }
    cout<<"MAX PARTY SIZE IS "<<S.calc()<<"\n";
    return;
}
 
int main() {
        ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>C;
    while(C--) {
        cin>>N>>M;
        comment.clear();
        for(int i = 0; i < M; i++){
            string inform;
            int a, b;
            cin>>inform>>a>>b;
            int tmp = (inform[0] == 'A' ? 1: -1); 
            comment.push_back( pair<int, pair<int, int> >(tmp,  make_pair(a, b)));
        }
        findContradiction();
    }
}

 

3. 초대 가능한 최대 사람 수 구하기

 

max party 의 크기는 다음과 같다 

 

아무것도 속해있지 않은 집합 의 크기

+

어느 한 집합과 그 집합과 반대되는 집합 두개 중 크기가 큰 집합의 크기

 

 

이러면 연결되지 않은 집합들 것 또한 신경 써서 초대할 수  있다.

 

 

EDITORWARS