fork download
copy 
  1. /*
  2. --------------              |   /
  3.       |                     |  /
  4.       |                     | /
  5.       |             *       |/          |    |         ------            *
  6.       |                     |           |    |        /      \
  7.       |             |       |\          |    |       |       |\          |
  8.    \  |             |       | \         |    |       |       | \         |
  9.     \ |             |       |  \        |    |        \     /   \        |
  10.      V              |       |   \        \__/|         -----     \       |
  11. */
  12. #include <bits/stdc++.h>
  13. using namespace std;
  14.  
  15. #ifdef EMT
  16. #define debug(x) cerr << "\e[1;31m" << #x << " = " << (x) << "\e[0m\n"
  17. #define print(x) emilia_mata_tenshi(#x, begin(x), end(x))
  18. template<typename T, typename T2> ostream& operator<<(ostream &os, const pair<T, T2> &obj) {
  19. 	return os << '{' << obj.first << ',' << obj.second << '}';
  20. }
  21. template<class TupType, size_t... I> void lamy_kawaii(ostream& os, const TupType& _tup, index_sequence<I...>) {
  22. 	// source: https://stackoverflow.com/a/41171552
  23. 	os << '{';
  24. 	(..., (cerr << (I == 0? "" : ",") << get<I>(_tup)));
  25. 	os << '}';
  26. }
  27. template<class... T> ostream& operator<<(ostream &os, const tuple<T...>& _tup) {
  28. 	lamy_kawaii(os, _tup, make_index_sequence<sizeof...(T)>());
  29. 	return os;
  30. }
  31. template<typename T> void emilia_mata_tenshi(const char *s, T l, T r) {
  32. 	cerr << "\e[1;33m" << s << " = [";
  33. 	while(l != r) {
  34. 		cerr << *l;
  35. 		cerr << (++l == r ? ']' : ',');
  36. 	}
  37. 	cerr << "\e[0m\n";
  38. }
  39. #else
  40. #define debug(x) 48763
  41. #define print(x) 48763
  42. #endif
  43.  
  44. template<typename T, typename T2> istream& operator>>(istream &is, pair<T, T2> &obj) {
  45. 	is >> obj.first >> obj.second;
  46. 	return is;
  47. }
  48. template<typename T> istream& operator>>(istream &is, vector<T> &obj) {
  49. 	for(auto &x : obj)
  50. 		is >> x;
  51. 	return is;
  52. }
  53.  
  54. #define YN(x) ((x) ? "YES" : "NO")
  55. #define yn(x) ((x) ? "Yes" : "No")
  56. #define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
  57. using ll = int64_t;
  58. using ull = uint64_t;
  59. using ld = long double;
  60. using uint = uint32_t;
  61. const double EPS  = 1e-8;
  62. const int INF     = 0x3F3F3F3F;
  63. const ll LINF     = 4611686018427387903;
  64. const int MOD     = 1e9+7;
  65. static int Lamy_is_cute = []() {
  66. 	EmiliaMyWife
  67. 	return 48763;
  68. }();
  69. /*--------------------------------------------------------------------------------------*/
  70.  
  71. struct find_bridges {
  72. 	int n, t;
  73. 	vector<vector<int>> edge;
  74. 	vector<bool> is;
  75. 	vector<pair<int, int>> edges;
  76. 	vector<int> tim, low;
  77. 	find_bridges() { }
  78. 	find_bridges(int _n) {
  79. 		n = _n;
  80. 		t = 1;
  81. 		edge.resize(n);
  82. 		tim.resize(n);
  83. 		low.resize(n);
  84. 	}
  85. 	void add_edge(int u, int v) {
  86. 		if(u != v) {
  87. 			edge[u].push_back(edges.size());
  88. 			edge[v].push_back(edges.size());
  89. 		}
  90. 		is.push_back(false);
  91. 		edges.push_back({u, v});
  92. 	}
  93. 	void dfs(int u, int p = -1) {
  94. 		tim[u] = low[u] = t++;
  95. 		for(int i : edge[u]) {
  96. 			if(i == p)
  97. 				continue;
  98. 			int v = edges[i].first;
  99. 			if(v == u)
  100. 				v = edges[i].second;
  101. 			if(tim[v])
  102. 				low[u] = min(low[u], tim[v]);
  103. 			else {
  104. 				dfs(v, i);
  105. 				if(low[v] > tim[u])
  106. 					is[i] = true;
  107. 				low[u] = min(low[u], low[v]);
  108. 			}
  109. 		}
  110. 	}
  111. 	int find() {
  112. 		for(int i = 0; i < n; i++)
  113. 			if(!tim[i])
  114. 				dfs(i);
  115. 		int ans = 0;
  116. 		for(int i = 0; i < edges.size(); i++)
  117. 			ans += is[i];
  118. 		return ans;
  119. 	}
  120. 	inline bool is_edge(int x) { return is[x]; }
  121. };
  122.  
  123. signed main() {
  124. 	int n, m;
  125. 	cin >> n >> m;
  126. 	auto bri = find_bridges(n);
  127. 	for(int i = 0; i < m; i++) {
  128. 		int u, v;
  129. 		cin >> u >> v;
  130. 		bri.add_edge(u - 1, v - 1);
  131. 	}
  132. 	cout << bri.find() << '\n';
  133. }
  134.  
Success #stdin #stdout 0.01s 5540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/qbSESl
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

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!