13344 - Chess Tournament

문제 링크

---

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

문제 요약

---

수식이 주어졌을 때 주어진 수식들이 일관성이 있는지 혹은 모순이 있는지 찾아내는 문제다.

문제 풀이

---

수식은 크게 두가지 종류가 존재한다.

1. \(u = v\) : \(u\)와 \(v\)는 같다

2. \(u \gt v\) : \(u\)가 \(v\)보다 크다

만약 1번 수식이 없다고 생각을 해보자. 1번 수식이 없고 2번 수식만 있을 때 주어진 수식들이 일관성이 있는지 없는지 어떻게 판단을 할 수 있을까? \(u\)와 \(v\)가 나오고 \(\gt\)가 화살표 처럼 생겼으므로 \(u\)에서 \(v\)로 향하는 방향 그래프를 만들어 보자. 이 때 만약 \(Cycle\)이 있으면 어떻게 될까? \(Cycle\)이 존재하도록 수식을 만들려고 한다면 모순이 생길수 밖에 없다는 것을 쉽게 알 수 있다. 방향 그래프에서 싸이클의 존재 유무는 Cycle Detection Algorithm을 통해 쉽게 판단할 수 있다.

자 이제 남은 문제는 1번 수식들만 잘 처리한다면 우리는 이 문제를 해결할 수 있다. 동등한 위치에 있는 변수들을 어떻게 하면 효과적으로 관리할 수 있을까? 우리는 \(Disjoint\ set\)을 알고 있으므로 이를 활용한다면 효율적으로 1번 수식들을 처리할 수 있다는것을 알 수 있다.

최종적으로는 \(Disjoint\ set\)으로 1번 수식들을 전부 처리한다음 2번 수식들을 방향 그래프로 모델링한 뒤 싸이클의 존재 유무를 찾는 알고리즘을 설계할 수 있다. 우리는 \(O(N+M)\)의 시간복잡도로 이 문제를 해결할 수 있다.

소스 코드

---

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct Union {
  vector<int> p, r;
  Union(int n) : p(n), r(n, 1) {
    for (int i = 0 ; i < n ; ++i) {
      p[i] = i;
    }
  }
  int find(int u) {
    if (u == p[u]) {
      return u;
    }
    return p[u] = find(p[u]);
  }
  void merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) {
      return;
    }
    
    if (r[u] > r[v]) {
      swap(u, v);
    }
    p[u] = v;
    if (r[u] == r[v]) {
      ++r[v];
    }
  }
};

int n, m, u, v, V[50010];
char op;
vector<pair<int, int>> vp;
vector<vector<int>> node;

bool findCycle(int here) {
  if (V[here]) {
    if (V[here] == -1) {
      return true;
    }
    return false;
  }
  
  V[here] = -1;
  for (int there : node[here]) {
    if (findCycle(there)) {
      return true;
    }
  }
  V[here] = 1;
  
  return false;
}

int main() {
  scanf("%d%d", &n, &m);
  Union uni(n);
  while (m--) {
    scanf("%d %c %d", &u, &op, &v);
    if (op == '=') {
      uni.merge(u, v);
    } else {
      vp.emplace_back(u, v);
    }
  }
  
  node.resize(n);
  for(auto& pii : vp) {
    u = uni.find(pii.first);
    v = uni.find(pii.second);
    node[u].push_back(v);
  }
  
  for (int i = 0 ; i < n ; ++i) {
    if (findCycle(i)) {
      puts("inconsistent");
      return 0;
    }
  }
  puts("consistent");
}