Submission #3588

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

C

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
int n,top2=-1,stack2[100001],stack[100001],top=-1,save[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;
	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(make_pair(list[k][save[k]],k),false));
				stack[++top]=list[k][save[k]];
				break;
			}
			else if(edge.find(make_pair(k,list[k][save[k]]))==edge.end()){
				edge.insert(make_pair(make_pair(list[k][save[k]],k),true));
				list2[list[k][save[k]]].push_back(k);
			}
		}
		if(save[k]==list[k].size()){
			top--;
			stack2[++top2]=k;
		}
	}
}
void flood(int k){
	int i;
	stack[++top]=k;
	while(top!=-1){
		k=stack[top];
		check[k]=1;
		for(;save[k]<list2[k].size();save[k]++){
			if(!check[list2[k][save[k]]]){
				it=edge.find(make_pair(k,list2[k][save[k]]));
				if(it->second){
					if(backedge)
						flag=1;
					backedge=1;
				}
				stack[++top]=list2[k][save[k]];
				break;
			}
		}
		if(save[k]==list2[k].size())
			top--;
	}
}
int main(){
	int m,i,a,b;
	freopen("input.txt","r",stdin);
	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));
	memset(save,0,sizeof(save));
	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: 0 / 1