BOJ 1765 - 닭싸움 팀 정하기 링크
(2023.08.18 기준 G2)

문제

n명의 학생들의 m개의 인간관계가 주어진다.
내 친구의 친구는 내 친구이며, 내 원수의 원수도 내 친구이다.

닭싸움 팀을 나눠야 하는데, 두 학생이 친구이면 같은 팀에 속해있어야 하며, 같은 팀에 속해 있는 사람들끼리는 전부 친구여야 한다.
닭싸움 팀의 최대 수 출력

알고리즘

분리 집합 및 그래프 분석

풀이

나 - 친구 A - 친구 B 관계에선 나와 친구 B가 친구가 된다. 이를 친구 A 관점에서 보면?
친구 A - 나 - 친구 B 관계에서 친구 A와 친구 B가 친구가 되는 것이다. 원수 관계에서도 마친가지로 관찰할 수 있는 점이다.

친구와 원수 관계를 나타내는 그래프를 완성한 뒤, 모든 학생마다 그 학생의 친구들끼리, 그리고 원수들끼리 한번 더 union 해주면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;

int pa[MAXN];

int find(int u){
    if (pa[u] != u) pa[u] = find(pa[u]);
    return pa[u];
}

void merge(int u, int v){
    u = find(u); v = find(v);
    if (u < v) pa[v] = u;
    else pa[u] = v;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;

    vector<int> F[n], E[n];
    iota(pa, pa + n, 0);

    char r; int p, q;
    while (m--){
        cin >> r >> p >> q;
        if (r == 'F'){
            F[--p].push_back(--q);
            F[q].push_back(p);
            merge(p, q); // 친구 관계이면 팀이 되어야 하므로 union
        }
        else{
            E[--p].push_back(--q);
            E[q].push_back(p);
        }
    }

    for (int i = 0; i < n; i++){

        // 친구 A - 나 - 친구 B 이면 친구 A와 친구 B도 친구 관계다.
        for (int j = 0, sz = E[i].size(); j < sz - 1; j++)
            for (int k = 1; k < sz; k++) merge(E[i][j], E[i][k]);

        // 원수 A - 나 - 원수 B 이면 원수 A와 원수 B는 친구 관계다.
        for (int j = 0, sz = F[i].size(); j < sz - 1; j++)
            for (int k = 1; k < sz; k++) merge(F[i][j], F[i][k]);
    }

    int result = 0; // 분리 집합의 개수가 곧 답이다.
    for (int i = 0; i < n; i++) if (find(i) == i) result++;
    cout << result;
}

• Python

import sys; input = sys.stdin.readline

def find(u):
    if pa[u] != u:
        pa[u] = find(pa[u])
    return pa[u]

def union(u, v):
    u = find(u)
    v = find(v)
    if u < v:
        pa[v] = u
    else:
        pa[u] = v

n = int(input())

F = [[] for _ in range(n)]
E = [[] for _ in range(n)]
pa = [i for i in range(n)]

for _ in range(int(input())):
    r, p, q = input().split()
    p = int(p) - 1; q = int(q) - 1
    if r == 'F':
        F[p].append(q)
        F[q].append(p)
        union(p, q) # 친구 관계이면 팀이 되어야 하므로 union
    else:
        E[p].append(q)
        E[q].append(p)

for i in range(n):

    # 친구 A - 나 - 친구 B 이면 친구 A와 친구 B도 친구 관계다.
    for j in range(len(E[i]) - 1):
        for k in range(1, len(E[i])):
            union(E[i][j], E[i][k])

    # 원수 A - 나 - 원수 B 이면 원수 A와 원수 B는 친구 관계다.
    for j in range(len(F[i]) - 1):
        for k in range(1, len(F[i])):
            union(F[i][j], F[i][k])

result = 0
for i in range(n):
    if find(i) == i: # 분리 집합의 개수가 곧 답이다.
        result += 1
print(result)