풀이
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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이