제출 #3754

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
3754		BalloonCollector	Cactus? Not cactus? (kriii1_C)	C++98	0 / 1	0 ms	3848 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;
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]);
	}
	sort(tmp.begin(),tmp.end());
	tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
	if(tmp.size()!=size)
	{
		size=tmp.size();
		for(int i=0; i<size; i++)
			cycle.push_back(tmp[i]);
	}
	else{
		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){
	
	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);
	sort(cycle.begin(),cycle.end());
	int size=cycle.size();
	cycle.erase(unique(cycle.begin(),cycle.end()),cycle.end());
	if(size!=cycle.size())
		puts("Not Cactus");
	else puts("Cactus");
	return 0;

}

• Subtask 1: 0 / 1