fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define pb push_back
  9. #define C make_pair
  10. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  11. #define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; i--)
  12. #define REP(i, n) for(int i = 0, _n = (n); i < _n; i++)
  13. #define MASK(i) (1LL << (i))
  14. #define BIT(i, x) ((x) & MASK(i))
  15. #define TURN_ON(i, x) ((x) | MASK(i))
  16. #define TURN_OFF(i, x) ((x) & ~MASK(i))
  17. #define REV(i, x) ((x) ^ MASK(i))
  18.  
  19. template<typename T>bool maximize(T &res, const T &a){if(res < a) return res = a, true; return false;}
  20. template<typename T>bool minimize(T &res, const T &a){if(res > a) return res = a, true; return false;}
  21.  
  22. const int maxn = (int)1e5 + 5;
  23. const ll MOD = (ll)1e9 + 7;
  24. const ll INF = (ll)1e15;
  25.  
  26. typedef pair<int, int> pi;
  27. typedef pair<int, pi> pii;
  28. typedef pair<ll, ll> pl;
  29. typedef pair<ll, pl> pll;
  30.  
  31. int n, m, low[10010], num[10010], child[10010], cnt, bridge, res;
  32. bool khop[10010];
  33. vector<int>a[10010];
  34.  
  35. void dfs(int u, int pre){
  36. 	num[u] = low[u] = ++cnt;
  37.  
  38. 	for(int v: a[u]){
  39. 		if(v == pre) continue;
  40. 		if(num[v]) minimize(low[u], num[v]);
  41. 		else{
  42. 			dfs(v, u);
  43. 			minimize(low[u], low[v]);
  44. 			child[u]++;
  45. 			if(low[v] > num[u]) bridge++;
  46. 			if(u == pre){
  47. 				if(child[u] >= 2) khop[u] = 1;
  48. 			}
  49. 			else if(low[v] >= num[u]) khop[u] = 1;
  50. 		}
  51. 	}
  52. }
  53. void nhap(){
  54. 	cin >> n >> m;
  55. 	FOR(i, 1, m){
  56. 		int u, v; cin >> u >> v;
  57. 		a[u].pb(v);
  58. 		a[v].pb(u);
  59. 	}
  60. }
  61. void solve(){
  62. 	FOR(i, 1, n) if(!num[i]) dfs(i, i);
  63. 	FOR(i, 1, n) if(khop[i]) res++;
  64. 	cout << res << " " << bridge;
  65. }
  66. int main(){
  67. 	ios_base::sync_with_stdio(0);
  68. 	cin.tie(0); cout.tie(0);
  69. 	nhap();
  70. 	solve();
  71. 	return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
10 12
1 10
10 2
10 3
2 4
4 5
5 2
3 6
6 7
7 3
7 8
8 9
9 7
stdout
copy 
4 3
https://ideone.com/3Sw1h7
language:
C++14 (gcc 8.3)
created:
1 day 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!