#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int N,M;
int visited_cnt;
map<pair<int,int>, int> visited_edge;
void cnt_cycle(vector<vector<int> > &graph, int &cnt, vector<int> &visited, int pre, int now){
//printf("cycle now == %d, pre == %d, visited_cnt = %d\n", now, pre, visited_cnt);
if(visited_cnt > M) return ;
visited_cnt++; // count edge
visited_edge[pair<int,int>(min(pre,now), max(pre,now))] = 1;
if(visited[now] != 0){
// printf("now == %d\n", now);
cnt++;
return;
}
visited[now] = 1;
for(int i=0;i<graph[now].size();i++){
int to = graph[now][i];
if( pre != to && visited_edge[pair<int,int>(min(now, to), max(now, to))] == 0 )
cnt_cycle(graph, cnt, visited, now, to);
}
}
int main(){
scanf("%d%d",&N,&M);
vector<vector<int> > graph(N + 1);
for(int i=0;i<M;i++){
int a,b; scanf("%d%d",&a,&b);
graph[a].push_back(b);
graph[b].push_back(a);
pair<int,int> tmp_edge(min(a,b), max(a,b));
visited_edge[tmp_edge] = 0;
}
int cnt = 0;
vector<int> visited(N+1, 0);
cnt_cycle(graph, cnt, visited, 0, 1);
//printf("cnt == %d\n",cnt);
if(cnt <= 1) printf("Cactus\n");
else printf("Not cactus\n");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
