#include <cstdio>
#include <vector>
#include <memory.h>
#include <map>
using namespace std;
const int MAX_N = 100001;
int N;
vector<int> adj[MAX_N];
vector<int> discovered;
vector<int> finished;
int time;
bool iscutVertex[MAX_N];
int no[MAX_N];
int t;
bool ans;
void input()
{
int m;
scanf("%d%d",&N,&m);
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
adj[a].push_back(b);
adj[b].push_back(a);
}
finished=discovered=vector<int>(N+1,-1);
memset(iscutVertex,false,sizeof(iscutVertex));
memset(no,0,sizeof(no));
time=0;
ans=true;
}
int DFS(int v,bool isRoot)
{
discovered[v]=time++;
int ret=discovered[v];
int children=0;
for(int i=0;i<adj[v].size();i++)
{
int there=adj[v][i];
if(discovered[there]==-1){
++children;
int subtree=DFS(there,false);
no[v]=subtree;
if(!isRoot&&subtree>=discovered[v])
{
iscutVertex[v]=true;
ret=min(ret,discovered[there]);
}
}
else
{//backedge
ret=min(ret,discovered[there]);
}
}
if(isRoot)iscutVertex[v]=(children>=2);
finished[v]=time++;
no[v]=ret;
return ret;
}
bool process()
{
for(int i=0;i<N;i++)
{
if(iscutVertex[i])
{
map<int,int> a;
for(int j=0;j<adj[i].size();j++)
{
int there=adj[i][j];
if(no[there]!=no[i])
{
a[no[i]]++;
}
if(a[no[i]]>1)return false;
}
}
}
return true;
}
int main()
{
input();
DFS(1,true);
if(process())printf("Cactus\n");
else printf("Not cactus\n");
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
4076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
