fork download 
  1.  
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5.  
  6. using namespace std;
  7.  
  8. struct node {
  9. 	int data, no;
  10. 	node *next;
  11. } *ge1[1000000], *ge2[1000000];
  12.  
  13. int dfn[1000000], low[1000000], up[1000000], queue[1000000], flag[1000000], e[2000000][2];
  14. bool bridge[2000000], del[2000000];
  15. int bufTop = 0, k;
  16.  
  17. void insertEdge(node *ge[], int a, int b, int c) {
  18. 	static node buf[4000000];
  19. 	node *p = &buf[bufTop ++];
  20. 	p->data = b;
  21. 	p->no = c;
  22. 	p->next = ge[a];
  23. 	ge[a] = p;
  24. }
  25.  
  26. void dfs(int i) {
  27. 	static int top = 0;
  28. 	dfn[i] = low[i] = top ++;
  29. 	for (node *p = ge1[i]; p; p = p->next) {
  30. 		if (p->data < k) continue;
  31. 		if (dfn[p->data] == -1) {
  32. 			up[p->data] = p->no;
  33. 			dfs(p->data);
  34. 			low[i] = min(low[i], low[p->data]);
  35. 			if (low[p->data] > dfn[i]) bridge[p->no] = true;
  36. 		} else if (p->no != up[i]) {
  37. 			low[i] = min(low[i], dfn[p->data]);
  38. 		}
  39. 	}
  40. }
  41.  
  42. int main() {
  43. 	int n, m, k;
  44. 	scanf("%d%d%d", &n, &m, &k);
  45. 	for (int i = 0; i < n; i ++) ge1[i] = 0;
  46. 	for (int i = 0; i < m; i ++) {
  47. 		scanf("%d%d", &e[i][0], &e[i][1]);
  48. 		e[i][0] --;
  49. 		e[i][1] --;
  50. 		insertEdge(ge1, e[i][0], e[i][1], i);
  51. 		insertEdge(ge1, e[i][1], e[i][0], i);
  52. 	}
  53.  
  54. 	memset(dfn, -1, sizeof(dfn));
  55. 	memset(bridge, false, sizeof(bridge));
  56. 	for (int i = k; i < n; i ++)
  57. 		if (dfn[i] == -1) {
  58. 			up[i] = -1;
  59. 			dfs(i);
  60. 		}
  61.  
  62. 	memset(flag, -1, sizeof(flag));
  63. 	for (int i = 0; i < k; i ++) flag[i] = i;
  64. 	int tot = k;
  65. 	for (int i = k; i < n; i ++)
  66. 		if (flag[i] == -1) {
  67. 			flag[i] = tot;
  68. 			queue[0] = i;
  69. 			for (int head = 0, tail = 1; head < tail; head ++)
  70. 				for (node *p = ge1[queue[head]]; p; p = p->next)
  71. 					if (p->data >= k && ! bridge[p->no] && flag[p->data] == -1) {
  72. 						flag[p->data] = tot;
  73. 						queue[tail ++] = p->data;
  74. 					}
  75. 			tot ++;
  76. 		}
  77.  
  78. 	for (int i = 0; i < tot; i ++) ge2[i] = 0;
  79. 	bufTop = 0;
  80. 	for (int i = 0; i < m; i ++)
  81. 		if (flag[e[i][0]] != flag[e[i][1]]) {
  82. 			insertEdge(ge2, flag[e[i][0]], flag[e[i][1]], i);
  83. 			insertEdge(ge2, flag[e[i][1]], flag[e[i][0]], i);
  84. 		}
  85.  
  86. 	memset(del, false, sizeof(del));
  87. 	memset(up, -1, sizeof(up));
  88. 	for (int i = 0; i < tot; i ++)
  89. 		if (up[i] == -1) {
  90. 			queue[0] = i;
  91. 			for (int head = 0, tail = 1; head < tail; head ++)
  92. 				for (node *p = ge2[queue[head]]; p; p = p->next)
  93. 					if (up[p->data] == -1 && p->data != i) {
  94. 						up[p->data] = p->no;
  95. 						queue[tail ++] = p->data;
  96. 					} else if (p->no != up[queue[head]]) {
  97. 						del[p->no] = true;
  98. 					}
  99. 		}
  100.  
  101. 	int cnt = 0;
  102. 	for (int i = 0; i < m; i ++)
  103. 		if (del[i]) cnt ++;
  104. 	printf("%d\n", cnt);
  105. 	for (int i = 0; i < m; i ++)
  106. 		if (del[i]) printf("%d %d\n", e[i][0] + 1, e[i][1] + 1);
  107.  
  108. 	return 0;
  109. }
  110.  
Success #stdin #stdout 0.03s 96448KB
comments (?)
stdin 
11 13 5
1 2
1 3
1 5
3 5
2 8
4 11
7 11
6 10
6 9
2 3
8 9
5 9
9 10
stdout 
3
3 5
2 8
2 3
https://ideone.com/RCIWZ
language:
C++ (gcc 8.3)
created:
14 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!