Submission #3781

#	Time	Username	Problem	Language	Result	Execution time	Memory
3781		cki86201	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	76 ms	12172 KiB

C

#include<stdio.h>
#include<vector>
using namespace std;

vector<int> edge[100000];
vector<int> now;
bool check[100000]={0};
bool check_cycle[100000]={0};
bool ans=false;
int distime[100000]={0},deltime[100000]={0},time=0;
void dfs(int a,int par){
	check[a]=true;
	distime[a]=time++;
	now.push_back(a);
	int i,j;
	for(i=0;i<edge[a].size();i++){
		if(check[edge[a][i]] && edge[a][i]!=par && distime[edge[a][i]]<distime[a]){
			if(check_cycle[edge[a][i]]){
				ans=true;
				return;
			}
			else{
				for(j=now.size()-1;j>=0;j--){
					check_cycle[now[j]]=true;
					if(now[j]==edge[a][i]) break;
				}
			}
		}
		else if(!check[edge[a][i]]){
			dfs(edge[a][i],a);
			if(ans) return;
		}
	}
	deltime[a]=time++;
	now.pop_back();
}
int main()
{
	int i,n,m,a,b;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d%d",&a,&b);
		edge[a-1].push_back(b-1);
		edge[b-1].push_back(a-1);
	}
	dfs(0,0);
	if(ans) printf("Not cactus");
	else printf("Cactus");
	return 0;
}

• Subtask 1: 0 / 1