Submission #4272

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4272	2013-09-10T01:43:28 Z	jays	Cactus? Not cactus? (kriii1_C)	C++	0 / 1	76 ms	13728 KB

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.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3944 KB	Output is correct
2	Correct	0 ms	3944 KB	Output is correct
3	Correct	0 ms	4096 KB	Output is correct
4	Correct	4 ms	3968 KB	Output is correct
5	Correct	4 ms	3944 KB	Output is correct
6	Correct	0 ms	4076 KB	Output is correct
7	Correct	4 ms	4076 KB	Output is correct
8	Correct	0 ms	4076 KB	Output is correct
9	Correct	4 ms	4076 KB	Output is correct
10	Correct	40 ms	6848 KB	Output is correct
11	Correct	20 ms	6696 KB	Output is correct
12	Correct	36 ms	9628 KB	Output is correct
13	Correct	52 ms	8292 KB	Output is correct
14	Correct	40 ms	8048 KB	Output is correct
15	Correct	40 ms	10812 KB	Output is correct
16	Correct	40 ms	8484 KB	Output is correct
17	Correct	32 ms	9828 KB	Output is correct
18	Correct	52 ms	12596 KB	Output is correct
19	Correct	76 ms	13728 KB	Output is correct
20	Correct	36 ms	8788 KB	Output is correct
21	Correct	60 ms	7960 KB	Output is correct
22	Correct	56 ms	11420 KB	Output is correct
23	Incorrect	0 ms	3944 KB	Output isn't correct
24	Halted	0 ms	0 KB	-