답안 #5195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5195	2014-02-14T08:45:53 Z	ainta	작은 사이클들 (YDX13_smallcycles)	C++	0 / 1	4 ms	4560 KB

E

#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);
}

Subtask #1

0.0 / 1.0

#	결과	실행 시간	메모리	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	-