-
Notifications
You must be signed in to change notification settings - Fork 4
/
775.cpp
64 lines (56 loc) · 1.29 KB
/
775.cpp
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
#include <iostream>
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
map<int, vector<int> > graph;
vector<int> curPath;
bool visited[300];
int n, a, b;
char in;
bool allVisited() {
for (int i = 1; i <= n; i++) if (not visited[i]) return false;
return true;
}
bool cycle(int start, int node) {
if (allVisited()) {
if (find(graph[node].begin(), graph[node].end(), start) != graph[node].end()) {
for (int i = 0; i < curPath.size(); i++)
cout << curPath[i] << ' ';
return true;
} else {
return false;
}
}
for (int i = 0; i < graph[node].size(); i++) {
if (not visited[graph[node][i]]) {
visited[graph[node][i]] = true;
curPath.push_back(graph[node][i]);
if (cycle(start, graph[node][i])) {
return true;
}
curPath.pop_back();
visited[graph[node][i]] = false;
}
}
return false;
}
int main() {
while (cin >> n) {
graph.clear();
while (scanf("%d %d\n", &a, &b)) {
graph[a].push_back(b);
graph[b].push_back(a);
}
cin >> in;
memset(visited, 0, sizeof(visited));
visited[1] = true;
curPath.clear();
curPath.push_back(1);
if (cycle(1, 1)) cout << 1 << endl;
else cout << 'N' << endl;
}
return 0;
}