[백준] 1765 - 닭싸움 팀 정하기

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

1765번: 닭싸움 팀 정하기

 

문제의 이해를 정말 잘해야 하는 문제이다.

보통의 친구 관계 문제에서는 한 연결 요소에서 관계가 "친구" 인지 "원수" 인지만 존재한다.

그래서 이 문제도 처음에 한 연결 요소 내에서 친구와 원수가 존재하는지만 판단하려고 했다.

 

하지만 이 문제에서

F 1 2

E 2 3

E 3 4

이런 관계에서는

1과 3이 원수관계 같지만, 사실 아무 관계도 아니다.

따라서 이 입력에서는

(1, 2, 4) (3) 이라는 팀이 만들어진다.

 

즉, 문제에 나와있는 "친구의 친구는 친구"와 "원수의 원수는 친구"만 확인하면 된다.

 

#include <iostream>
#include <vector>
using namespace std;

int n, m, vis[1001];
vector<vector<pair<int, int>>> v;

void go(int node) {
    vis[node] = 1;

    for (auto &i : v[node]) {
        if (!vis[i.first] && i.second == 1) {
            go(i.first);
        } else if (i.second == 0) {
            for (auto &j : v[i.first]) {
                if (!vis[j.first] && j.second == 0) {
                    go(j.first);
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    v.resize(n + 1);
    for (int i = 0; i < m; i++) {
        char a;
        int b, c;
        cin >> a >> b >> c;
        if (a == 'E') {
            v[b].push_back({c, 0});
            v[c].push_back({b, 0});
        } else {
            v[b].push_back({c, 1});
            v[c].push_back({b, 1});
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            go(i);
            ans++;
        }
    }

    cout << ans;
}