Submission #4273

#	Time	Username	Problem	Language	Result	Execution time	Memory
4273		jays	Cactus? Not cactus? (kriii1_C)	C++98	1 / 1	68 ms	13728 KiB

C

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

int N, M;
vector<int> adj[100001];
int depth[100001];
bool isCactus = true;

int dfs(int to, int from, int d) {
	int numBack = 0;
	int ret = depth[to] = d;
	for (int i = 0 ; i < adj[to].size(); ++i) {
		int next = adj[to][i];
		if (next == from) continue;
		if (depth[next] != -1 && depth[next] < depth[to]) {
			numBack++;
			ret = depth[next];
		}
		if (depth[next] != -1) continue;
		int res = dfs(next, to, d + 1);
		// printf("res: %d, depth[to]: %d\n", res, depth[to]);
		if (res <= depth[to]) {
			numBack++;
			ret = min(ret, res);
		}
	}
	if (numBack > 1) isCactus = false;
	return ret;
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		adj[x-1].push_back(y-1);
		adj[y-1].push_back(x-1);
	}
	memset(depth, -1, sizeof(depth));
	dfs(0, -1, 0);
	if (isCactus)
		printf("Cactus\n");
	else
		printf("Not cactus\n");
	return 0;
}

• Subtask 1: 1 / 1