답안 #5195

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5195 2014-02-14T08:45:53 Z ainta 작은 사이클들 (YDX13_smallcycles) C++
0 / 1
4 ms 4560 KB
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[100010];
int n, num[100001], cnt, par[100010], res;
bool chk[100010];
void DFS(int a){
	num[a] = ++cnt;
	int i, x, c = 0;
	for (i = 0; i < E[a].size(); i++){
		if (num[E[a][i]]){
			if (E[a][i] != par[a] && num[E[a][i]] < num[a]){
				x = a;
				while (x != E[a][i]){
					chk[x] = true;
					x = par[x];
				}
			}
			continue;
		}
		par[E[a][i]] = a;
		DFS(E[a][i]);
		if (!chk[E[a][i]])c++;
	}
	res += c / 2;
	if (c % 2 == 1 && !chk[a]){
		chk[a] = true;
		res++;
	}
}
int main()
{
	int i, m, a, b;
	scanf("%d%d", &n, &m);
	while (m--){
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	DFS(1);
	printf("%d\n", res);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 4428 KB Output is correct
2 Correct 0 ms 4428 KB Output is correct
3 Correct 0 ms 4428 KB Output is correct
4 Correct 0 ms 4428 KB Output is correct
5 Correct 0 ms 4428 KB Output is correct
6 Incorrect 4 ms 4560 KB Output isn't correct
7 Halted 0 ms 0 KB -