[백준/BOJ] 백준 13344번 : Chess Tournament

www.acmicpc.net/problem/13344

13344번: Chess Tournament

유니온 파인드를 이용하여 같은 능력의 플레이어는 묶는다. 그리고 묶은 집합을 이용하는데, 이기는 쪽으로 이동하는 집합으로 가는 집합 그래프를 만든다. 그리고 집합들의 위상 정렬을 이용해 문제를 해결하는데, 방문한 적이 있는 곳을 또 방문한다면 일관성이 없는 것이다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
using namespace std;

int n, m;
vector<pair<int, int>> bigger;
vector<int> parent(50000);
vector<int> rank_size(50000);
vector<int> indegree(50000);
vector<int> visited(50000);
vector<int> adj[50000];
set<int> set_check; //집합
int set_num = 0; //집합의 개수
int visited_num = 0; //방문한 집합의 개수

void Pre()
{
	for (int i = 0; i < 50000; i++)
	{
		parent[i] = i;
		rank_size[i] = 1;
		indegree[i] = 0;
		visited[i] = 0;
	}
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;

	if (rank_size[u] < rank_size[v])
	{
		parent[u] = v;
	}

	else
	{
		parent[v] = u;

		if (rank_size[u] == rank_size[v])
			rank_size[u]++;
	}
}

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

	Pre();

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int k, l;
		char command;

		cin >> k >> command >> l;

		//같은 능력의 플레이어는 묶는다
		if (command == '=')
		{
			Merge(k, l);
		}

		//승,패 정보를 저장한다
		else if (command == '>')
		{
			bigger.push_back(make_pair(k, l));
		}
	}

	//집합의 개수를 구한다
	for (int i = 0; i < n; i++)
	{
		int set_i = Find(i);
		if (set_check.count(set_i) == 0)
		{
			set_check.insert(set_i);
			set_num++;
		}
	}

	for (int i = 0; i < bigger.size(); i++)
	{
		int big = bigger[i].first;
		int small = bigger[i].second;

		int set_u = Find(big);
		int set_v = Find(small);

		//같은 집합인데 차이가 있을때
		if (set_u == set_v)
		{
			cout << "inconsistent";
			return 0;
		}

		//이기는쪽으로 이동하는 그래프를 만든다
		indegree[set_u]++;
		adj[set_v].push_back(set_u);
	}

	queue<int> q;
	set<int> q_insert_check; //큐에 들어간 집합 번호 체크
	for (int i = 0; i < n; i++)
	{
		int set_i = Find(i); //i의 집합 번호

		//이기는게 없는 집합이고, 큐에 들어가지 않은 집합일때
		if (indegree[set_i] == 0 && q_insert_check.count(set_i) == 0)
		{
			q.push(set_i);
			q_insert_check.insert(set_i);
		}
	}

	while (!q.empty())
	{
		int here = q.front();
		q.pop();
		visited[here] = 1;
		visited_num++;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];

			//방문한적 있는곳을 또 방문하는것 일때
			if (visited[there] == 1)
			{
				cout << "inconsistent";
				return 0;
			}

			indegree[there]--;

			if (indegree[there] == 0)
			{
				q.push(there);
			}

		}
	}

	if (visited_num == set_num)
		cout << "consistent";
	else
		cout << "inconsistent";

	return 0;
}