Submission #3563

#	Time	Username	Problem	Language	Result	Execution time	Memory
3563		mjy0503	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	176 ms	27212 KiB

C

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
int n,top=-1,stack[100001];
using namespace std;
vector<int> list[100001],list2[100001];
map<pair<int,int>,bool> edge;
map<pair<int,int>,bool>::iterator it;
bool check[100001],flag,backedge;
void back(int k){
	int i;
	check[k]=1;
	for(i=0;i<list[k].size();i++){
		if(!check[list[k][i]]){
			list2[list[k][i]].push_back(k);
			edge.insert(make_pair(make_pair(list[k][i],k),false));
			back(list[k][i]);
		}
		else if(edge.find(make_pair(k,list[k][i]))==edge.end()){
			edge.insert(make_pair(make_pair(list[k][i],k),true));
			list2[list[k][i]].push_back(k);
		}
	}
	stack[++top]=k;
}
void flood(int k){
	int i;
	check[k]=1;
	for(i=0;i<list2[k].size();i++){
		if(!check[list2[k][i]]){
			it=edge.find(make_pair(k,list2[k][i]));
			if(it->second){
				if(backedge)
					flag=1;
				backedge=1;
			}
			flood(list2[k][i]);
		}
	}
	stack[++top]=k;
}
int main(){
	int m,i,a,b;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d %d",&a,&b);
		a--;b--;
		list[a].push_back(b);
		list[b].push_back(a);
	}
	for(i=0;i<n;i++){
		if(!check[i])
			back(i);
	}
	memset(check,0,sizeof(check));
	for(;top>=0;top--){
		backedge=0;
		if(!check[stack[top]])
			flood(stack[top]);
	}
	if(flag)
		printf("Not cactus\n");
	else
		printf("Cactus\n");
	return 0;
}

• Subtask 1: 0 / 1