#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int N, M;
vector<int> adj[100001];
int depth[100001];
bool isCactus = true;
int dfs(int to, int from, int d) {
int numBack = 0;
int ret = depth[to] = d;
for (int i = 0 ; i < adj[to].size(); ++i) {
int next = adj[to][i];
if (next == from) continue;
if (depth[next] != -1 && depth[next] < depth[to]) {
numBack++;
ret = depth[next];
}
if (depth[next] != -1) continue;
int res = dfs(next, to, d + 1);
// printf("res: %d, depth[to]: %d\n", res, depth[to]);
if (res <= depth[to]) {
numBack++;
ret = min(ret, res);
}
}
if (numBack > 1) isCactus = false;
return ret;
}
int main() {
scanf("%d%d", &N, &M);
for (int i = 0; i < M; ++i) {
int x, y;
scanf("%d%d", &x, &y);
adj[x-1].push_back(y-1);
adj[y-1].push_back(x-1);
}
memset(depth, -1, sizeof(depth));
dfs(0, -1, 0);
if (isCactus)
printf("Cactus\n");
else
printf("Not cactus\n");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3940 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3940 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4088 KB |
Output is correct |
| 4 |
Correct |
4 ms |
3972 KB |
Output is correct |
| 5 |
Correct |
0 ms |
3940 KB |
Output is correct |
| 6 |
Correct |
0 ms |
4072 KB |
Output is correct |
| 7 |
Correct |
4 ms |
4072 KB |
Output is correct |
| 8 |
Correct |
0 ms |
4072 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4072 KB |
Output is correct |
| 10 |
Correct |
36 ms |
6844 KB |
Output is correct |
| 11 |
Correct |
24 ms |
6692 KB |
Output is correct |
| 12 |
Correct |
32 ms |
9624 KB |
Output is correct |
| 13 |
Correct |
48 ms |
8288 KB |
Output is correct |
| 14 |
Correct |
48 ms |
8048 KB |
Output is correct |
| 15 |
Correct |
48 ms |
10804 KB |
Output is correct |
| 16 |
Correct |
40 ms |
8344 KB |
Output is correct |
| 17 |
Correct |
32 ms |
9828 KB |
Output is correct |
| 18 |
Correct |
68 ms |
12592 KB |
Output is correct |
| 19 |
Correct |
60 ms |
13728 KB |
Output is correct |
| 20 |
Correct |
32 ms |
8784 KB |
Output is correct |
| 21 |
Correct |
56 ms |
7828 KB |
Output is correct |
| 22 |
Correct |
44 ms |
11408 KB |
Output is correct |
| 23 |
Correct |
0 ms |
3940 KB |
Output is correct |
| 24 |
Correct |
0 ms |
3940 KB |
Output is correct |
| 25 |
Correct |
8 ms |
4672 KB |
Output is correct |
| 26 |
Correct |
52 ms |
6712 KB |
Output is correct |
| 27 |
Correct |
24 ms |
4996 KB |
Output is correct |
| 28 |
Correct |
48 ms |
6316 KB |
Output is correct |
| 29 |
Correct |
52 ms |
6316 KB |
Output is correct |
| 30 |
Correct |
40 ms |
6448 KB |
Output is correct |
| 31 |
Correct |
48 ms |
6316 KB |
Output is correct |
| 32 |
Correct |
56 ms |
6712 KB |
Output is correct |
| 33 |
Correct |
56 ms |
6712 KB |
Output is correct |
| 34 |
Correct |
56 ms |
6712 KB |
Output is correct |
