16168 : 퍼레이드

풀이

degree 짝수가 어쩌구 저쩌구 해서 풀어도 되는데

그냥 제곱 돌려도 된다.

근데 degree 어쩌구 저쩌구 할 때 유의해야 할 점은

connected graph가 아닐 수도 있어서

유니온파인드 같은 걸 해줘야한다.

잘 짜주면 된다.

코드

#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

int n, m, chk[3003][3003];
vector<int> gph[3003];

void dfs(int now, int num, int cnt) {
    if (cnt == m) {
        puts("YES");
        exit(0);
    }
    for (int nxt : gph[now]) {
        if (chk[now][nxt] == num || chk[nxt][now] == num) continue;
        chk[now][nxt] = chk[nxt][now] = num;
        dfs(nxt, num, cnt+1);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        gph[u].push_back(v);
        gph[v].push_back(u);
    }
    
    for (int i = 1; i <= n; i++) {
        dfs(i, i, 0);
    }

    puts("NO");

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-10-01 09:47

Read more posts by this author