취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13344번 문제인 Chess Tournament이다.
문제는 아래 링크를 확인하자.

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

A > B와 같은 관계를 A에서 B로 가는 에지로 하는 방향그래프를 만들었을 때, 사이클이 존재한다면 inconsistent한 입력이고, 그렇지 않다면 consistent한 입력이 될 것이다.

단, C = D와 같은 관계가 있다면 C와 D를 같은 점으로 취급할 수 있으므로, 이것을 disjoint set을 이용하여 관리해주자.

아래는 제출한 소스코드이다.

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

int uf[50001];
int findf(int x) {
	if (x == uf[x]) return x;
	return uf[x] = findf(uf[x]);
}

vector<pair<int, int>> queries;

vector<int> G[50001];
bool visited[50001];
bool done[50001];

bool chk = 0;

void dfs(int current) {
	visited[current] = 1;
	int oldnode = 0;
	for (auto node : G[current]) {
		if (node == oldnode) continue;
		oldnode = node;
		if (visited[node]) {
			if (!done[node]) chk = 1;
			continue;
		}
		dfs(node);
	}
	done[current] = 1;
}

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

	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; i++) uf[i] = i;

	while (M--) {
		int x, y; char c; cin >> x >> c >> y;
		x++; y++;
		if (c == '=') {
			x = findf(x), y = findf(y);
			uf[y] = x;
		}
		else queries.push_back({ x,y });
	}

	for (auto q : queries) {
		int x = findf(q.first), y = findf(q.second);
		G[x].push_back(y);
	}

	for (int i = 1; i <= N; i++) sort(G[i].begin(), G[i].end());

	int num = 1;
	for (int i = 1; i <= N; i++) {
		if (visited[i]) continue;
		dfs(i);
		num++;
	}

	if (chk) cout << "inconsistent";
	else cout << "consistent";
}