#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
int n,top2=-1,stack2[200001],stack[200001],top=-1,save[200001];
using namespace std;
vector<int> list[200001],list2[200001];
map<pair<int,int>,bool> edge;
map<pair<int,int>,bool>::iterator it;
bool check[100001],flag,backedge;
void back(int k){
int i;
stack[++top]=k;
while(top!=-1){
k=stack[top];
check[k]=1;
for(;save[k]<list[k].size();save[k]++){
if(!check[list[k][save[k]]]){
list2[list[k][save[k]]].push_back(k);
edge.insert(make_pair(make_pair(list[k][save[k]],k),false));
stack[++top]=list[k][save[k]];
break;
}
else if(edge.find(make_pair(k,list[k][save[k]]))==edge.end()){
edge.insert(make_pair(make_pair(list[k][save[k]],k),true));
list2[list[k][save[k]]].push_back(k);
}
}
if(save[k]==list[k].size()){
top--;
stack2[++top2]=k;
}
save[k]++;
}
}
void flood(int k){
int i;
stack[++top]=k;
while(top!=-1){
k=stack[top];
check[k]=1;
for(;save[k]<list2[k].size();save[k]++){
it=edge.find(make_pair(k,list2[k][save[k]]));
if(it->second){
if(backedge)
flag=1;
backedge=1;
}
if(!check[list2[k][save[k]]]){
stack[++top]=list2[k][save[k]];
break;
}
}
if(save[k]==list2[k].size())
top--;
}
}
int main(){
int m,i,a,b;
scanf("%d %d",&n,&m);
for(i=0;i<m;i++){
scanf("%d %d",&a,&b);
a--;b--;
list[a].push_back(b);
list[b].push_back(a);
}
for(i=0;i<n;i++){
if(!check[i])
back(i);
}
for(i=0;i<n;i++){
check[i]=0;save[i]=0;
}
for(;top2>=0;top2--){
backedge=0;
if(!check[stack2[top2]])
flood(stack2[top2]);
}
if(flag)
printf("Not cactus\n");
else
printf("Cactus\n");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
13028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
