Submission #3822

# Submission time Handle Problem Language Result Execution time Memory
3822 2013-08-31T08:35:43 Z BalloonCollector Cactus? Not cactus? (kriii1_C) C++
0 / 1
0 ms 3948 KB
#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;

}
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3948 KB Output isn't correct
2 Halted 0 ms 0 KB -