oj.uz

답안 #4133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4133 2013-09-02T09:08:03 Z pys7293 Cactus? Not cactus? (kriii1_C) C++
0 / 1
 4 ms 3684 KB 
#include <algorithm>
#include <cstdio>
#include <map>
#include <memory.h>
#include <vector>

using namespace std;

int N, M;
int Lv[111111], C;
int Lo[111111];

map<int, map<int, bool> > Chk;

vector<vector<int> > L;

void DFS(int i, int P)
{
	if (Lv[i] == 0) Lv[i] = Lo[i] = ++C;
	for (int j = 0; j < L[i].size(); j++) {
		if (P == L[i][j]) continue;
		if (Lv[L[i][j]] == 0) {
			DFS(L[i][j], i);
			Lo[i] = min(Lo[i], Lo[L[i][j]]);
			if (Lv[i] > 1 && Lv[i] < Lo[L[i][j]]) Chk[i][L[i][j]] = Chk[L[i][j]][i] = true;
		} else Lo[i] = min(Lo[i], Lo[L[i][j]]);
	}
}

int main(void)
{
	scanf("%d%d", &N, &M);
	L.resize(N + 1);
	for (int i = 1; i <= M; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		L[u].push_back(v);
		L[v].push_back(u);
	}
	if (L[1].size() == 1) Chk[1][L[1][0]] = Chk[L[1][0]][1] = true;
	DFS(1, 0);
	bool Ans = true;
	for (int i = 1; i <= N; i++) {
		if (!Ans) break;
		int CC = 0;
		for (int j = 0; j < L[i].size(); j++) {
			if (Chk[i][L[i][j]]) continue;
			CC++;
		}
		if (!(CC == 0 || CC == 2)) Ans = false;
	}
	printf("%s\n", Ans ? "Cactus" : "Not cactus");

	return 0;
}

Subtask #1
0.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2120 KB Output is correct
2 Correct 0 ms 2120 KB Output is correct
3 Correct 4 ms 3684 KB Output is correct
4 Correct 0 ms 3464 KB Output is correct
5 Correct 4 ms 3136 KB Output is correct
6 Correct 4 ms 3176 KB Output is correct
7 Incorrect 4 ms 2648 KB Output isn't correct
8 Halted 0 ms 0 KB -