Submission #16431

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

C

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;


int N,M;
int visited_cnt;
map<pair<int,int>, int> visited_edge;


void cnt_cycle(vector<vector<int> > &graph, int &cnt, vector<int> &visited, int pre, int now){
	//printf("cycle now == %d, pre == %d, visited_cnt = %d\n", now, pre, visited_cnt);
	if(visited_cnt > M) return ;
	visited_cnt++; // count edge

	visited_edge[pair<int,int>(min(pre,now), max(pre,now))] = 1;
	if(visited[now] != 0){
	//	printf("now == %d\n", now);
		cnt++;
		return;
	}

	visited[now] = 1;
	for(int i=0;i<graph[now].size();i++){
		int to = graph[now][i];
		if( pre != to && visited_edge[pair<int,int>(min(now, to), max(now, to))] == 0 )
			cnt_cycle(graph, cnt, visited, now, to);
	}
}

int main(){
	scanf("%d%d",&N,&M);
	vector<vector<int> > graph(N + 1);
	for(int i=0;i<M;i++){
		int a,b; scanf("%d%d",&a,&b);
		graph[a].push_back(b);
		graph[b].push_back(a);
		pair<int,int> tmp_edge(min(a,b), max(a,b));
		visited_edge[tmp_edge] = 0;
	}
	int cnt = 0;
	vector<int> visited(N+1, 0);
	cnt_cycle(graph, cnt, visited, 0, 1);

	//printf("cnt == %d\n",cnt);
	if(cnt <= 1) printf("Cactus\n");
	else printf("Not cactus\n");
	return 0;
}

• Subtask 1: 0 / 1