Submission #3804

# Submission time Handle Problem Language Result Execution time Memory
3804 2013-08-31T08:26:17 Z shinhj88 Cactus? Not cactus? (kriii1_C) C++
0 / 1
0 ms 4076 KB
#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");
}
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4076 KB Output isn't correct
2 Halted 0 ms 0 KB -