백준 23818 (C++) 원수의 원수

최초 업로드: 2025-10-06 12:20:24

최근 수정 시간: 2025-10-06 12:22:43

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] 원수의 원수

[문제 링크](https://www.acmicpc.net/problem/23818)

## 문제 설명

원수의 원수는 친구라는 속담이 있다! 이 속담과 함께라면 어떤 두 사람이든 그 쌍의 관계를 알 수 있다. A와 C라는 사람이 직접적으로 관계가 없더라도, A와 B가 관계가 있고 B와 C가 관계가 있다면 A와 C라는 사람도 간접적으로 관계가 있다. 이를 정리하면 아래와 같다.

이를 바탕으로 사람들 간의 관계가 주어질 때, 특정 사람 간의 관계가 무엇인지를 확인해보자!

## 입력

사람의 수 $N \, (2 \leq N \leq 100,000)$과 관계의 수 $M \, (0\leq M \leq 100,000)$, 그리고 대답해야 할 관계의 수 $K \, (1\leq K \leq 100,000)$가 입력으로 들어온다.

그 후 $M$개의 줄에 걸쳐 $t \in \{0, 1\}$, $a$, $b$ $(1\leq a, b \leq N, a \neq b)$가 입력으로 들어오게 된다.

$t$ = 0일 경우 $a$, $b$가 친구 관계임을 의미한다.

$t$ = 1일 경우 $a$, $b$가 원수 관계임을 의미한다.

그 후 $K$개의 줄에 걸쳐 쿼리 $a$, $b$ $(1\leq a, b \leq N, a \neq b)$가 입력으로 들어오게 된다.

## 출력

각 쿼리에 대해 $a$와 $b$의 관계를 각 줄마다 출력하면 된다.

$a$와 $b$가 전혀 관련이 없을 경우 'Unknown'을 출력한다.

$a$와 $b$가 친구 관계인 경우 'Friend'를 출력한다.

$a$와 $b$가 원수 관계인 경우 'Enemy'를 출력한다.

$a$와 $b$가 친구 관계이자 원수 관계인 경우 'Error'를 출력한다.

## 풀이
분리 집합으로 각각의 정점이 어느 컴포넌트에 속하는지 구분해주었고, dfs로 각각의 컴포넌트를 이분 그래프로 색칠하다(친구인 경우는 이전 정점과 같은 색으로, 원수인 경우는 이전 정점과 다른 색으로) 색칠이 불가능한 경우에 해당 컴포넌트에 속한 정점을 모두 에러로 기록했습니다.  
쿼리에서 a와 b가 서로 다른 컴포넌트에 속해있으면 'Unknown', 에러 컴포넌트에 속해있느면 'Error', 같은 색이면 "Friend', 다른 색이면 'Enemy'를 출력해주었습니다.

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

const int MAX = 100'001;

int parent[MAX], error[MAX], color[MAX];
vector<vector<pair<int, int>>> conn(MAX);

int _find(int x) {
    if(x==parent[x]) return x;
    return parent[x] = _find(parent[x]);
}

void _union(int x, int y) {
    x = _find(x);
    y = _find(y);
    if(x>y) parent[x]=y;
    else parent[y]=x;
}

void dfs(int cur, int curColor, int prv) {
    color[cur] = curColor;
    for(auto next:conn[cur]) {
        if(color[next.first]==-1) dfs(next.first, curColor^next.second, cur);
        else if(color[next.first]!=curColor^next.second) error[_find(next.first)]=true;
    }
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, m, k; cin >> n >> m >> k;
 for(int i=1;i<=n;i++) parent[i]=i;

while(m--) {
        int t, a, b; cin >> t >> a >> b;
        _union(a, b);
        conn[a].push_back({b, t});
        conn[b].push_back({a, t});
    }

memset(color, -1, sizeof color);
 for(int i=1;i<=n;i++) {
 if(parent[i]==i) {
 dfs(i, 0, -1);
 }
 }

while(k--) {
 int a, b; cin >> a >> b;
 if(_find(a)!=_find(b)) cout << "Unknown\n";
 else if(error[_find(a)]) cout << "Error\n";
 else if(color[a]==color[b]) cout << "Friend\n";
 else cout << "Enemy\n";
 }
}
```