fork(2) download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <vector>
  4. #include <queue>
  5. #include <map>
  6. using namespace std;
  7.  
  8. vector<int> r[200100];
  9. vector<int> b[200100];
  10.  
  11. int rG[200100];
  12. int bVisit[200100];
  13. int ans[200100];
  14. int N, B, R;
  15.  
  16.  
  17. int idx = 1;
  18. void rbfs(int start) {
  19. 	queue<int> q;
  20. 	rG[start] = idx;
  21. 	q.push(start);
  22. 	while (q.empty() == false) {
  23. 		int s = q.front();
  24. 		q.pop();
  25. 		int len = r[s].size();
  26. 		for (int i = 0; i < len; i++) {
  27. 			int next = r[s][i];
  28. 			if (rG[next] != 0) continue;
  29. 			q.push(next);
  30. 			rG[next] = idx;
  31. 		}
  32. 	}
  33. 	idx++;
  34. }
  35.  
  36. void bbfs(int start) {
  37.  
  38. 	queue<int> q;
  39. 	q.push(start);
  40. 	map<int, vector<int>*> m;
  41. 	bVisit[start] = 1;
  42. 	m[rG[start]] = new vector<int>();
  43. 	m[rG[start]]->push_back(start);
  44. 	while (q.empty() == false) {
  45. 		int s = q.front();
  46. 		q.pop();
  47. 		int len = b[s].size();
  48. 		for (int i = 0; i < len; i++) {
  49. 			int next = b[s][i];
  50. 			if (bVisit[next] == 0) {
  51. 				bVisit[next] = 1;
  52. 				if (m.find(rG[next]) == m.end()) {
  53. 					m[rG[next]] = new vector<int>();
  54. 				}
  55. 				m[rG[next]]->push_back(next);
  56. 			}
  57. 		}
  58. 	}
  59.  
  60. 	for (auto it = m.begin(); it != m.end(); it++) {
  61. 		vector<int>* v = it->second;
  62. 		int len = v->size();
  63. 		for (int i = 0; i < len; i++) {
  64. 			ans[(*v)[i]] = v->size();
  65. 		}
  66. 		delete v;
  67. 	}
  68. }
  69.  
  70. int main() {
  71. 	//freopen("Text.txt", "r", stdin);
  72. 	scanf("%d %d %d", &N, &R, &B);
  73. 	for (int i = 0; i < R; i++) {
  74. 		int s, e;
  75. 		scanf("%d %d", &s, &e);
  76. 		r[s].push_back(e);
  77. 		r[e].push_back(s);
  78. 	}
  79. 	for (int i = 0; i < B; i++) {
  80. 		int s, e;
  81. 		scanf("%d %d", &s, &e);
  82. 		b[s].push_back(e);
  83. 		b[e].push_back(s);
  84. 	}
  85. 	for (int i = 1; i <= N; i++) {
  86. 		if (rG[i] == 0) {
  87. 			rbfs(i);
  88. 		}
  89. 	}
  90.  
  91. 	for (int i = 1; i <= N; i++) {
  92. 		if (bVisit[i] == 0) {
  93. 			bbfs(i);
  94. 		}
  95. 	}
  96. 	for (int i = 1; i <= N; i++) {
  97. 		printf("%d ", ans[i]);
  98. 	}
  99. 	return 0;
  100. }
Success #stdin #stdout 0s 13132KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rGd1fD
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!