https://www.acmicpc.net/problem/13023
13023번: ABCDE
문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.
www.acmicpc.net
A, B, C, D, E가 아니다!
이런 관계를 가진 사람들이 있는지 확인하는 문제.
전형적인 DFS 문제이다.
DFS 돌리고 깊이가 5가 되면 1 출력
아니면 0 출력
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include <iostream>
#include <vector>
using namespace std;
static vector<vector<int>> A;
static vector<bool> visited;
// 도착 확인 변수, 1 or 0 출력 결정
static bool arrive;
void DFS(int now, int depth)
{
if (depth == 5 || arrive)
{
arrive = true;
return;
}
visited[now] = true;
for (int i : A[now])
{
if (!visited[i])
{
DFS(i, depth + 1);
}
}
visited[now] = false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
arrive = false;
cin >> n >> m;
A.resize(n);
visited = vector<bool>(n, false);
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
A[u].push_back(v);
A[v].push_back(u);
}
for (int i = 0; i < n; i++)
{
DFS(i, 1);
if (arrive)
{
break;
}
}
if (arrive)
{
cout << 1 << '\n';
}
else
{
cout << 0 << '\n';
}
return 0;
}
|
cs |
