fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. ////////////// Prewritten code follows. Look down for solution. ////////////////
  5.  
  6. #define fs first
  7. #define sc second
  8. #define pb push_back
  9. #define len(x) ((int)(x).size())
  10. #define all(x) (x).begin(), (x).end()
  11. #define rall(x) (x).rbegin(), (x).rend
  12. #define forn(i, n) for(int i = 0; i < (int)(n); ++i)
  13. #define for1(i, n) for(int i = 1; i <= (int)(n); ++i)
  14. #define ford(i, n) for(int i = (int)(n); i >= 0; --i)
  15. #define fore(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
  16.  
  17. typedef pair<int, int> pii;
  18. typedef vector<int> vi;
  19. typedef vector<pii> vpi;
  20. typedef vector<vi> vvi;
  21. typedef long long ll;
  22. typedef pair<ll, ll> pll;
  23. typedef vector<ll> vl;
  24. typedef vector<vl> vll;
  25.  
  26. template<typename T> void maxself(T &a, T &b){a = max(a, b);};
  27. template<typename T> void minself(T &a, T &b){a = min(a, b);};
  28.  
  29. const ll LINF = 1e18;
  30. const int INF = 1e9;
  31. const int MOD = 1e9+7;
  32.  
  33. /// command for char arrays with spaces -> scanf(" %[^\n]", text);
  34.  
  35. ////////////////////////// Solution starts below. //////////////////////////////
  36.  
  37. const int N = 1e4+5;
  38. vvi adj;
  39. vi dfsChildren, dfsNum, dfsLow, dfsParent;
  40. bitset<N> artV;
  41. int dfsTime, root, rootChildren;
  42.  
  43. void init(int n){
  44. 	adj.clear();
  45. 	adj.resize(n);
  46. 	dfsNum.clear();
  47. 	dfsNum.resize(n, 0);
  48. 	dfsLow.clear();
  49. 	dfsLow.resize(n, 0);
  50. 	dfsParent.clear();
  51. 	dfsParent.resize(n, 0);
  52. 	dfsChildren.clear();
  53. 	dfsChildren.resize(n, 0);
  54. 	artV.reset();
  55. }
  56.  
  57. bool comp(int &a, int &b){
  58. 	if(dfsChildren[a] == dfsChildren[b]){
  59. 		return a < b;
  60. 	}
  61. 	return dfsChildren[a] > dfsChildren[b];
  62. }
  63.  
  64. void dfs(int v){
  65. 	dfsNum[v] = dfsLow[v] = dfsTime++;
  66. 	for(int u : adj[v]){
  67. 		if(!dfsNum[u]){
  68. 			dfsParent[u] = v;
  69. 			dfsChildren[v]++;
  70. 			if(v == root) rootChildren++;
  71. 			dfs(u);
  72. 			if(u != root and dfsLow[u] >= dfsNum[v]){
  73. 				artV[v] = 1;
  74. 			}
  75. 			minself(dfsLow[v], dfsLow[u]);
  76. 		}else if(u != dfsParent[v]){
  77. 			minself(dfsLow[v], dfsNum[u]);
  78. 		}
  79. 	}
  80. }
  81.  
  82. int main(){
  83.  
  84. 	int n, m;
  85. 	while(scanf("%d %d", &n, &m), n || m){
  86. 		init(n);
  87. 		int a, b;
  88. 		while(true){
  89. 			scanf("%d %d", &a, &b);
  90. 			if(a < 0 and b < 0) break;
  91. 			adj[a].pb(b);
  92. 			adj[b].pb(a);
  93. 		}
  94. 		dfsTime = 1;
  95. 		forn(i, n){
  96. 			if(!dfsNum[i]){
  97. 				root = i;
  98. 				rootChildren = 0;
  99. 				dfs(root);
  100. 				if(rootChildren > 1){
  101. 					artV[root] = 1;
  102. 				}
  103. 			}
  104. 		}
  105. 		vector<int> ans;
  106. 		forn(i, n){
  107. 			if(artV[i])
  108. 				ans.pb(i);
  109. 		}
  110. 		if(len(ans) < m){
  111. 			forn(i, n){
  112. 				if(!artV[i]) ans.pb(i);
  113. 				if(len(ans) == m) break;
  114. 			}
  115. 		}
  116. 		sort(all(ans), comp);
  117. 		for(int v : ans){
  118. 			printf("%d %d\n", v, dfsChildren[v]);
  119. 		}
  120. 	}
  121.  
  122. 	return 0;
  123. }
Success #stdin #stdout 0s 4572KB
comments (?)
stdin
copy 
8 4
0 4
1 2
2 3
2 4
3 5
3 6
3 7
6 7
-1 -1
0 0
stdout
copy 
2 2
3 2
0 1
4 1
https://ideone.com/OO4Kdn
language:
C++14 (gcc 8.3)
created:
4 years 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!