Graph And Its Complement

문제

링크: Graph And Its Complement

난이도: 1700

풀이

일반성을 잃지 않고 $a \geq b$라 합시다. 그렇지 않은 경우 출력할 때 $0$와 $1$을 바꿔서 출력하면 됩니다. (self-loop 간선 제외)

$G$의 연결 요소가 $2$개 이상, 즉 $a \geq 2$라고 하고, 그 중 임의의 연결 요소 두 개를 골라 $P$, $Q$라고 합시다.

임의의 정점 $p \in P$와 $q \in Q$에 대해 $G$에서 간선 $(p, q)$가 존재하지 않으므로 $H$에서 간선 $(p, q)$가 존재합니다. 따라서 $p$와 $q$는 $H$에서 같은 연결 요소에 속합니다.

임의의 정점 $u, v \in P$와 $w \in Q$에 대해 $G$에서 간선 $(u, w)$와 $(v, w)$가 존재하지 않으므로 $H$에서 간선 $(u, w)$와 $(v, w)$가 존재합니다. 따라서 $u$와 $v$는 $H$에서 같은 연결 요소에 속해 있습니다.

임의의 정점을 두 개 골랐을 떄 같은 연결 요소에 속하든 다른 연결 요소에 속하든 $H$에서는 항상 연결되어 있습니다. 따라서 $a \geq 2$이려면 $b = 1$이어야 합니다.

해당 경우는 간선 $(i, i + 1)$을 $i = 1$부터 순서대로 사용하여 연결 요소의 개수를 조절하는 방법으로 해결할 수 있습니다.

남은 $a = b = 1$인 경우를 살펴봅시다.

$n > 3$인 경우 아까와 같이 간선 $(i, i + 1)$을 모두 사용하는 방법으로 해결할 수 있습니다.

$n = 2$ 혹은 $n = 3$인 경우에는 어떠한 방법으로도 조건을 만족하는 그래프를 구성할 수 없음을 완전 탐색으로 증명할 수 있습니다.

$n = 1$인 경우는 아무 간선도 사용하지 않는 경우밖에 없고, 이는 $a = b = 1$를 만족하므로 해가 존재합니다.

코드

#include <bits/stdc++.h>
using namespace std;
 
bool ans[1010][1010];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, a, b;
    cin >> n >> a >> b;
 
    if (2 <= n and n <= 3 and a == 1 and b == 1) {
        cout << "NO";
        return 0;
    }
 
    if (a > 1 and b > 1) {
        cout << "NO";
        return 0;
    }
    cout << "YES\n";
 
    bool swapped = (a == 1);
    if (swapped) swap(a, b);
    fill(&ans[0][0], &ans[n][n] + 1, swapped);
    for (int i = 1; i <= n; i++) ans[i][i] = false;
 
    for (int i = 2; i - 1 <= n - a; i++) {
        ans[i - 1][i] = ans[i][i - 1] = not swapped;
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << ans[i][j];
        }
        cout << '\n';
    }
 
    return 0;
}