| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 3688 | mjy0503 | Cactus? Not cactus? (kriii1_C) | C++98 | 0 ms | 0 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 <string.h>
#include <vector>
#include <set>
int n,top2=-1,stack2[200001],stack[200001],top=-1,save[200001],cnt[200001];
using namespace std;
vector<int> list[200001],list2[200001];
set<pair<int,int>> edge;
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(list[k][save[k]],k));
stack[++top]=list[k][save[k]];
break;
}
else if(edge.find(make_pair(k,list[k][save[k]]))==edge.end()){
edge.insert(make_pair(list[k][save[k]],k));
cnt[list[k][save[k]]]++;
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,sum=0;
stack[++top]=k;
while(top!=-1){
k=stack[top];
if(!check[k])
sum+=cnt[k];
check[k]=1;
for(;save[k]<list2[k].size();save[k]++){
if(!check[list2[k][save[k]]]){
stack[++top]=list2[k][save[k]];
break;
}
}
if(save[k]==list2[k].size())
top--;
}
if(sum>=2)
flag=1;
}
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;
}