Submission #3783

#	Time	Username	Problem	Language	Result	Execution time	Memory
3783		shinhj88	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	0 ms	4072 KiB

C

#include <cstdio>
#include <vector>
#include <memory.h>
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])
		{
			for(int j=0;j<adj[i].size();j++)
			{
				int there=adj[i][j];
				if(no[there]!=no[i])return false;
			}
		}
	}
	return true;

}
int main()
{
	input();
	DFS(1,true);
	if(process())printf("Cactus\n");
	else printf("Not cactus\n");
}

• Subtask 1: 0 / 1