# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
5120 | ainta | Cactus? Not cactus? (kriii1_C) | C++98 | 76 ms | 12840 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<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int par[100010], num[100100], C;
bool chk[100010], ck;
vector<int>E[100010];
int n;
void DFS(int a, int p){
par[a] = p;
num[a] = ++C;
int i, x;
for (i = 0; i < E[a].size(); i++){
if (E[a][i] == p)continue;
if (par[E[a][i]]){
if (num[E[a][i]] > num[a])continue;
x = a;
while (x != E[a][i]){
ck |= chk[x];
chk[x] = true;
if (ck)return;
x = par[x];
}
ck |= chk[x];
chk[x] = true;
if (ck)return;
}
else DFS(E[a][i], a);
if (ck)return;
}
}
int main(){
int i, a, b, m;
scanf("%d%d", &n, &m);
while (m--){
scanf("%d%d", &a, &b);
E[a].push_back(b);
E[b].push_back(a);
}
DFS(1, 1);
printf(ck ? "Not Cactus\n" : "Cactus\n");
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |