fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> adj[5000];
  5. int cnt[5000], dfsn[5000], dcnt;
  6.  
  7. int dfs(int now, int prv) {
  8. 	int tmp, ret = dfsn[now] = dcnt++;
  9.  
  10. 	for (int nxt : adj[now]) if (nxt != prv) {
  11. 		if (dfsn[nxt] == -1) tmp = dfs(nxt, now);
  12. 		else {
  13. 			tmp = dfsn[nxt];
  14. 			if (tmp > dfsn[now]) continue;
  15. 		}
  16.  
  17. 		if (tmp >= dfsn[now]) ++cnt[now];
  18. 		ret = min(ret, tmp);
  19. 	}
  20.  
  21. 	if (prv == -1) cnt[now] = max(0, cnt[now] - 1);
  22. 	return ret;
  23. }
  24. int solution(int n, vector<vector<int>> edges) {
  25. 	for (auto &i : edges) {
  26. 		adj[--i[0]].push_back(--i[1]);
  27. 		adj[i[1]].push_back(i[0]);
  28. 	}
  29.  
  30. 	memset(dfsn, -1, sizeof(dfsn));
  31. 	dfs(0, -1);
  32.  
  33. 	int ans = 0;
  34. 	for (int i = 0; i < n; ++i)
  35. 		if (edges.size() - adj[i].size() + cnt[i] < n - 1) ans += i + 1;
  36.  
  37. 	return ans;
  38. }
  39.  
  40. int main() {
  41. 	cout << solution(4, { { 1, 2 }, { 1, 3 }, { 2, 3 }, { 2, 4 }, { 3, 4 } });
  42. 	return 0;
  43. }
Success #stdin #stdout 0s 4528KB
comments (?)
stdin 
Standard input is empty
stdout 
5
https://ideone.com/bhTfJu
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!