Submission #3699

#	Time	Username	Problem	Language	Result	Execution time	Memory
3699		mjy0503	Cactus? Not cactus? (kriii1_C)	C++98	1 / 1	180 ms	24632 KiB

C

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
int n,top2=-1,stack2[200001],stack[200001],top=-1,save[200001],cnt[200001];
using namespace std;
vector<int> list[200001],list2[200001];
set< pair<int,int> > edge;
bool check[100001],flag,backedge;
void back(int k){
	int i;
	stack[++top]=k;
	while(top!=-1){
		k=stack[top];
		check[k]=1;
		for(;save[k]<list[k].size();save[k]++){
			if(!check[list[k][save[k]]]){
				list2[list[k][save[k]]].push_back(k);
				edge.insert(make_pair(list[k][save[k]],k));
				stack[++top]=list[k][save[k]];
				break;
			}
			else if(edge.find(make_pair(k,list[k][save[k]]))==edge.end()){
				edge.insert(make_pair(list[k][save[k]],k));
				cnt[list[k][save[k]]]++;
				list2[list[k][save[k]]].push_back(k);
			}
		}
		if(save[k]==list[k].size()){
			top--;
			stack2[++top2]=k;
		}
		save[k]++;
	}
}
void flood(int k){
	int i,sum=0;
	stack[++top]=k;
	while(top!=-1){
		k=stack[top];
		if(!check[k])
			sum+=cnt[k];
		check[k]=1;
		for(;save[k]<list2[k].size();save[k]++){
			if(!check[list2[k][save[k]]]){
				stack[++top]=list2[k][save[k]];
				break;
			}
		}
		if(save[k]==list2[k].size())
			top--;
	}
	if(sum>=2)
		flag=1;
}
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);
	}
	for(i=0;i<n;i++){
		check[i]=0;save[i]=0;
	}
	for(;top2>=0;top2--){
		backedge=0;
		if(!check[stack2[top2]])
			flood(stack2[top2]);
	}
	if(flag)
		printf("Not cactus\n");
	else
		printf("Cactus\n");
	return 0;
}

• Subtask 1: 1 / 1