#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int,int> ii;
map <ii,bool> mp;
vector<int> e[100001],cycle;
int n,m,a,b,f;
bool ch[100001];
void dfs(int v, vector<int> d){
vector<int> tmp;
int size=d.size();
for(int i=0; i<size; i++){
tmp.push_back(d[i]);
}
tmp.push_back(v);
for(int i=size-2; i>=0; i--){
if(tmp[i]==v){
for(int j=i+1; j<size; j++){
if(ch[tmp[j]])
f=1;
ch[i]=1;
}
}
}
if(f)
return ;
size=e[v].size();
for(int i=0; i<size; i++){
if(!mp[ii(v,e[v][i])]){
mp[ii(v,e[v][i])]=1;
mp[ii(e[v][i],v)]=1;
//tmp.push_back(e[v][i]);
dfs(e[v][i],tmp);
//tmp.pop_back();
}
}
}
int main(void){
//freopen("input.txt","r",stdin);
scanf("%d %d",&n,&m);
for(int i=0; i<m; i++){
scanf("%d %d",&a,&b);
e[a].push_back(b);
e[b].push_back(a);
}
vector<int> tmp;
//tmp.push_back(a);
dfs(a,tmp);
if(f)
puts("Not Cactus");
else puts("Cactus");
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
3948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
