Submission #5196

#	Time	Username	Problem	Language	Result	Execution time	Memory
5196		ainta	작은 사이클들 (YDX13_smallcycles)	C++98	1 / 1	76 ms	12908 KiB

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);
	}
	chk[1] = true;
	DFS(1);
	printf("%d\n", res);
}

• Subtask 1: 1 / 1