IOI2020 Day1 supertrees 풀이

문제 및 채점: oj.uz

 

정점이 $N$ 개인 양방향 그래프가 있다. 이 그래프에서 정점 $i$와 정점 $j$ 사이의 단순 경로의 수는 $p[i][j]$이다. $p[i][i] = 1$이며, $0 \leq p[i][j] \leq 3$이다. $p$ 배열의 내용만 주어졌을 때, 원래 그래프를 복원하는 것이 가능한지 확인하고, 가능하다면 그래프를 복원하는 문제다.

 

서브태스크 1 (11 점)

$p[i][j] = 1$이다. 트리에서 각 정점 사이에 경로는 항상 한 개만 존재한다는 사실을 생각해보자. 즉, 모든 트리에 대해 $p[i][j] = 1$이기 때문에, 아무 트리로 그래프를 복원하면 된다. 아래는 만들 수 있는 단순한 트리 중 하나다.

서브태스크 2 (10 점)

$p[i][j] = 0\ \mathrm{or}\ 1$이다. 서브태스크 1과의 차이로는 $p[i][j] = 0$이 될 수 있는 거고, 경우에 따라서 복원이 불가능할 수 있다. $p[i][j] = 0$인 경우, 정점 $i$와 정점 $j$는 서로 다른 연결 요소에 있는 것이고, 한 연결 요소의 모양은 서브태스크 1에서의 그래프 모양과 같다.

 

서브태스크 3 (19 점)

$p[i][j] = 0\ \mathrm{or}\ 2$이다. 서브태스크 2에서처럼 그래프는 여러 연결 요소들로 이루어질 수 있으며, 같은 연결 요소 안에 있는 정점 사이에 있는 단순 경로의 수는 모두 2이므로, 연결 요소는 아래와 같이 고리 모양으로 구성된다.

서브태스크 4 (35 점)

$p[i][j] \leq 2$이며, 그래프의 복원이 항상 가능하다. 그래프의 복원이 항상 가능하기 때문에 그래프의 복원 가능 여부를 구하는 로직을 구현하지 않아도 된다. 임의의 서로 다른 두 정점 사이의 단순 경로 개수가 2개가 되기 위해서는 고리가 한 개 필요하며, 같은 연결 요소 안에 고리가 여러 개인 경우 단순 경로의 개수는 2개보다 많아진다. 연결 요소에 고리가 1개 있는 경우 단순 경로의 수가 어떤 식으로 계산되는지 확인해보자.

가운데에 1-2-3-4-5-6으로 구성된 고리(싸이클)가 있다. 이 고리에 속한 정점을 고리 정점이라고 하자. 고리에 속하지 않은 각 정점들은 한 개의 고리 정점과 연결되어 있다. 고리 정점을 포함하여 그 고리 정점에 연결된 고리에 속하지 않은 정점들 사이의 단순 경로의 개수는 1이며, 다른 고리 정점과, 다른 고리 정점에 연결된 고리에 속하지 않은 정점들 사이의 단순 경로의 개수는 2이다. 예를 들어, 정점 3, 정점 7, 정점 8, 정점 9는 고리 정점을 포함하여 같은 고리 정점에 연결되어 있으며, 이들 사이의 단순 경로의 개수는 1이며, 이 정점들과 다른 정점 사이의 단순 경로의 개수는 모두 2이다. 이러한 관찰을 통해 union-find를 사용하여 그래프를 복원할 수 있다.

 

서브태스크 5 (21 점)

서브태스크 4에서처럼 그래프를 복원하고, 실제로 그 그래프에서 정점 사이의 단순 경로 개수를 계산하여 $p$ 배열과 값을 비교하여 복원이 가능한지 여부를 확인하면 된다.

 

서브태스크 6 (4 점)

$p[i][j] \leq 3$이다. 이전 서브태스크와 달리 $p[i][j] = 3$인 경우가 생긴다. 임의의 서로 다른 두 정점 사이의 단순 경로의 수가 2보다 커지기 위해서는 필연적으로 연결 요소에서 고리의 개수가 1개보다 많아야 한다. 고리가 2개인 아무 그래프나 그렸을 때, 임의의 서로 다른 두 정점 사이의 단순 경로의 수가 3보다 많아지는 경우가 반드시 있음을 알 수 있다. 때문에 $p[i][j] = 3$인 경우가 있으면, 그래프의 복원은 항상 불가능하다.

 

#include <bits/stdc++.h> #include "supertrees.h" using namespace std; int construct(vector<vector<int>> p) { int N = p.size(); for (int i=0;i<N;i++) for (int j=0;j<N;j++) if (p[i][j] == 3) return 0; vector<vector<int>> answer(N, vector<int>(N, 0)); // union-find vector<int> line(N, 0), compo(N, 0); for (int i=0;i<N;i++) line[i] = compo[i] = i; function<int(int, vector<int>&)> find; find = [&](int n, vector<int> &par){ return par[n] == n ? n : par[n] = find(par[n], par); }; auto _union = [&](vector<int> &par, int a, int b){ par[find(b, par)] = find(a, par); }; for (int i=0;i<N;i++) for (int j=i+1;j<N;j++){ if (p[i][j]) _union(compo, i, j); if (p[i][j] == 1) _union(line, i, j); } for (int i=0;i<N;i++) find(i, compo), find(i, line); auto connect = [&](int a, int b){ answer[a][b] = answer[b][a] = 1; }; for (int i=0;i<N;i++) if (compo[i] == i){ vector <int> cycle; for (int j=0;j<N;j++) if (compo[j] == i && line[j] == j) cycle.push_back(j); int n = cycle.size(); if (n == 1) continue; if (n == 2) return 0; for (int j=0;j<n;j++) connect(cycle[j], cycle[(j+1)%n]); } for (int i=0;i<N;i++) if (line[i] != i) connect(line[i], i); for (int i=0;i<N;i++) for (int j=i+1;j<N;j++){ if (line[i] == line[j]){ if (p[i][j] != 1) return 0; } else if (compo[i] == compo[j]){ if (p[i][j] != 2) return 0; }else{ if (p[i][j] != 0) return 0; } } build(answer); return 1; }