Submission #16429

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

C

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

int N,M;
int visited_cnt;

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

	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)
			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);
	}
	int cnt = 0;
	vector<int> visited(N+1, 0);
	cnt_cycle(graph, cnt, visited, 0, 1);
	if(cnt <= 1) printf("Cactus\n");
	else printf("Not cactus\n");
	return 0;
}

• Subtask 1: 0 / 1