Submission #4272

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

C

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

using namespace std;

const int MAX_N = 100001;

int N, M;
vector<int> adj[MAX_N];

bool isCactus = true;
int d[MAX_N]; vector<bool> visited; int cnt = 0;

int dfs(int u) {
	visited[u] = true;
	int ret = d[u] = cnt++;
	int numBack = 0;
	for (int i = 0; i < adj[u].size(); ++i) {
		int v = adj[u][i];
		if (!visited[v]) { 
			int res = dfs(v);
			if (res < d[u]) {
				numBack++;
				ret = res;
			}
		}
		if (d[v] != -1 && d[v] < d[u]) {
			numBack++;
			ret = min(ret, d[v]);
		}
	}
	if (numBack > 2)
		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(d, -1, sizeof(d));
	visited = vector<bool>(N, false);
  	dfs(0);
	if (isCactus)
      printf("Cactus\n");
	else
      printf("Not cactus\n");
	return 0;
}

• Subtask 1: 0 / 1