제출 #469867

#제출 시각아이디문제언어결과실행 시간메모리
4698671bin산만한 고양이 (KOI17_cat)C++14
33 / 100
280 ms59000 KiB
#include <bits/stdc++.h>
#include <cassert>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e5 + 5;
ll n, m, a, b, dfsn[NMAX], cnt[NMAX], y[NMAX], t, ans, sum, tmp[NMAX];
vector<int> adj[NMAX];

void dfs(int now, int bef) {
	dfsn[now] = ++t;
	ll x = 0;

	for (int nx : adj[now]) {
		if (nx == bef) continue;
		if (!dfsn[nx]) {
			dfs(nx, now);
			cnt[now] += cnt[nx]; y[now] += y[nx];
			tmp[now] += tmp[nx];
		}
		else if (dfsn[nx] < dfsn[now]) x++, cnt[bef]++, tmp[now]++;
		else x++, cnt[now]--, y[bef]++;
	}
	assert(tmp[now] == x + y[now] + cnt[now]);
	if (!y[now] && cnt[now] <= 1 && !(sum - x - y[now] - cnt[now])) ans += now;
	return;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> m;
	sum = m - (n - 1);
	while (m--) {
		cin >> a >> b;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	dfs(1, 0);
	cout << ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...