# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
152635 | ansol4328 | Cactus? Not cactus? (kriii1_C) | C++11 | 90 ms | 12024 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<bits/stdc++.h>
using namespace std;
int n, m;
vector<int> lst[100005];
bool visit[100005], cyc[100005];
int cnt, cur[100005], vlst[100005];
bool cactus=true;
void dfs(int v, int prev)
{
if(cur[v]!=0){
if(cactus){
for(int i=cur[v] ; i<=cnt ; i++){
if(cyc[vlst[i]]) cactus=false;
cyc[vlst[i]]=true;
}
}
return;
}
if(visit[v]) return;
cnt++;
visit[v]=true;
cur[v]=cnt;
vlst[cnt]=v;
for(int i=0 ; i<lst[v].size() ; i++){
int nxt=lst[v][i];
if(nxt!=prev) dfs(nxt,v);
}
cnt--;
cur[v]=0;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1 ; i<=m ; i++){
int x, y;
scanf("%d %d",&x,&y);
lst[x].push_back(y);
lst[y].push_back(x);
}
for(int i=1 ; i<=n ; i++) if(!visit[i]) dfs(i,-1);
printf("%s",cactus ? "Cactus" : "Not cactus");
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |