# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
4150 | pys7293 | Cactus? Not cactus? (kriii1_C) | C++98 | 76 ms | 15104 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <algorithm>
#include <cstdio>
#include <map>
#include <memory.h>
#include <vector>
using namespace std;
int N, M;
int Lv[111111], C;
int Lo[111111];
int Chk[111111];
int P[111111];
vector<vector<int> > L;
void DFS(int i, int PP)
{
if (Lv[i] == 0) Lv[i] = Lo[i] = ++C;
for (int j = 0; j < L[i].size(); j++) {
if (PP == L[i][j]) continue;
if (Lv[L[i][j]] == 0) {
P[L[i][j]] = i;
DFS(L[i][j], i);
Lo[i] = min(Lo[i], Lo[L[i][j]]);
if (Lv[i] < Lo[L[i][j]]) Chk[L[i][j]] = true;
} else Lo[i] = min(Lo[i], Lv[L[i][j]]);
}
}
int main(void)
{
scanf("%d%d", &N, &M);
L.resize(N + 1);
for (int i = 1; i <= M; i++) {
int u, v;
scanf("%d%d", &u, &v);
L[u].push_back(v);
L[v].push_back(u);
}
DFS(1, 0);
bool Ans = true;
for (int i = 1; i <= N; i++) {
if (!Ans) break;
int CC = 0;
for (int j = 0; j < L[i].size(); j++) {
if (i == P[L[i][j]] && Chk[L[i][j]]) continue;
if (L[i][j] == P[i] && Chk[i]) continue;
CC++;
}
if (!(CC == 0 || CC == 2)) Ans = false;
}
printf("%s\n", Ans ? "Cactus" : "Not cactus");
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |