#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;
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]);
}
sort(tmp.begin(),tmp.end());
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
if(tmp.size()!=size)
{
size=tmp.size();
for(int i=0; i<size; i++)
cycle.push_back(tmp[i]);
}
else{
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){
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);
sort(cycle.begin(),cycle.end());
int size=cycle.size();
cycle.erase(unique(cycle.begin(),cycle.end()),cycle.end());
if(size!=cycle.size())
puts("Not Cactus");
else puts("Cactus");
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
3848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
