14412번: Ronald

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


$O(n^2)$

클릭이 두 개이하이고 모든 꼭지점에 이들 집합에 속해 있을 때 가능하고, 그 이외의 경우 불가능하다.

#include<cstdio>
int n, m, x, y, c[1001][1001];
int main() {
    for (scanf("%d%d", &n, &m); m--;) {
        scanf("%d%d", &x, &y);
        c[x][y] = c[y][x] = 1;
    }
    for (int i = 2; i <= n; i++) for (int j = 2; j < i; j++) if (c[1][i] ^ c[1][j] == c[i][j]) {
        puts("NE");
        return 0;
    }
    puts("DA");
    return 0;
}