#include <cstdio>
#include <vector>
using namespace std;
typedef pair <int, int> ii;
int ch[100002], che[100002];
vector <ii> v[100002];
int cycle = 0;
void dfs(int u){
if( ch[u] ) return ;
ch[u] = 1;
int si = v[u].size();
for(int i=0; i<si; i++){
if( !che[v[u][i].second] ){
che[v[u][i].second] = 1;
if( !ch[v[u][i].first] )
dfs( v[u][i].first );
else{
cycle ++;
}
}
}
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
for(int i=0; i<m; i++){
int x, y;
scanf("%d %d", &x, &y);
v[x].push_back(ii(y, i));
v[y].push_back(ii(x, i));
}
dfs( 1 );
if( cycle < 2 ) printf("Cactus\n");
else printf("Not cactus\n");
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
4332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
