Submission #3822

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

C

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int,int> ii;
map <ii,bool> mp;
vector<int> e[100001],cycle;
int n,m,a,b,f;
bool ch[100001];
void dfs(int v, vector<int> d){
	vector<int> tmp;
	int size=d.size();
	for(int i=0; i<size; i++){
		tmp.push_back(d[i]);
	}
	tmp.push_back(v);
	for(int i=size-2; i>=0; i--){
		if(tmp[i]==v){
			for(int j=i+1; j<size; j++){
				if(ch[tmp[j]])
					f=1;
				ch[i]=1;
			}
		}
	}
	if(f)
		return ;
	size=e[v].size();
	for(int i=0; i<size; i++){
		if(!mp[ii(v,e[v][i])]){
			mp[ii(v,e[v][i])]=1;
			mp[ii(e[v][i],v)]=1;
				//tmp.push_back(e[v][i]);
			dfs(e[v][i],tmp);
				//tmp.pop_back();
		}
	
	}

}
int main(void){
	//freopen("input.txt","r",stdin);
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++){
		scanf("%d %d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	vector<int> tmp;
	//tmp.push_back(a);
	dfs(a,tmp);
	
	if(f)
		puts("Not cactus");
	else puts("Cactus");
	return 0;

}

• Subtask 1: 0 / 1