fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
  6. template<class A, class B> bool minimize(A& x, B y) {if (x >= y) return x = y, true; else return false;}
  7.  
  8. typedef     long long             ll;
  9. typedef     unsigned long long    ull;
  10. typedef     double                db;
  11. typedef     long double           ld;
  12. typedef     pair<db, db>          pdb;
  13. typedef     pair<ld, ld>          pld;
  14. typedef     pair<int, int>        pii;
  15. typedef     pair<ll, ll>          pll;
  16. typedef     pair<ll, int>         plli;
  17. typedef     pair<int, ll>         pill;
  18.  
  19. #define     all(a)                a.begin(), a.end()
  20. #define     pb(a)                 push_back(a)
  21. #define     pf(a)                 push_front(a)
  22. #define     fi                    first
  23. #define     se                    second
  24. // #define     int                   long long
  25.  
  26. const int MAX_N = 1e5 + 5;
  27.  
  28. int n, m, numQ;
  29. int root[MAX_N];
  30. vector<pii> edgeColor[MAX_N];
  31. vector<int> adj[MAX_N];
  32. int ans[MAX_N];
  33. vector<pii> q[MAX_N];
  34. vector<int> colorList[MAX_N];
  35. map<pii, int> id;
  36. int qId[MAX_N];
  37.  
  38. int findRoot(int u) {
  39. 	return root[u] = (root[u] == u ? u : findRoot(root[u]));
  40. }
  41.  
  42. void unionSet(int u, int v) {
  43. 	int rootU = findRoot(u);
  44. 	int rootV = findRoot(v);
  45. 	if (rootU != rootV) {
  46. 		root[rootU] = rootV;
  47. 	}
  48. }
  49.  
  50. signed main() {
  51. 	ios_base::sync_with_stdio(false);
  52. 	cin.tie(nullptr);
  53.  
  54. 	cin >> n >> m;
  55. 	for (int i = 1; i <= n; i++) {
  56. 		root[i] = i;
  57. 	}
  58. 	for (int i = 1; i <= m; i++) {
  59. 		int u, v, c;
  60. 		cin >> u >> v >> c;
  61. 		edgeColor[c].pb(make_pair(u, v));
  62. 		colorList[c].pb(u);
  63. 		colorList[c].pb(v);
  64. 		adj[u].pb(v);
  65. 		adj[v].pb(u);
  66. 	}
  67.  
  68. 	for (int i = 1; i <= n; i++) {
  69. 		sort(all(adj[i]));
  70. 		adj[i].erase(unique(all(adj[i])), adj[i].end());
  71. 	}
  72.  
  73. 	for (int i = 1; i <= m; i++) {
  74. 		sort(all(colorList[i]));
  75. 		colorList[i].erase(unique(all(colorList[i])), colorList[i].end());
  76. 	}
  77.  
  78. 	cin >> numQ;
  79. 	for (int i = 1; i <= numQ; i++) {
  80. 		int u, v;
  81. 		cin >> u >> v;
  82. 		if (adj[u].size() > adj[v].size()) swap(u, v);
  83. 		auto InsId = id.insert({{u, v}, 0});
  84. 		if (InsId.se) {
  85. 			InsId.fi->se = i;
  86. 			q[u].pb(make_pair(v, i));
  87. 		}
  88. 		qId[i] = InsId.fi->se;
  89. 	}
  90.  
  91. 	for (int c = 1; c <= m; c++) {
  92. 		for (auto it : edgeColor[c]) {
  93. 			unionSet(it.fi, it.se);
  94. 		}
  95. 		for (auto u : colorList[c]) {
  96. 			for (auto it : q[u]) {
  97. 				ans[it.se] += (findRoot(u) == findRoot(it.fi));
  98. 			}
  99. 		}
  100. 		for (auto u : colorList[c]) {
  101. 			root[u] = u;
  102. 		}
  103. 	}
  104.  
  105. 	for (int i = 1; i <= numQ; i++) {
  106. 		cout << ans[qId[i]] << '\n';
  107. 	}
  108.  
  109. 	return 0;
  110. }
  111.  
  112. /*
  113.  
  114.  
  115. */
Success #stdin #stdout 0.01s 13220KB
comments (?)
stdin 
5 7
1 5 1
2 5 1
3 5 1
4 5 1
1 2 2
2 3 2
3 4 2
5
1 5
5 1
2 5
1 5
1 4
stdout 
1
1
1
1
2
https://ideone.com/2jnspf
language:
C++14 (gcc 8.3)
created:
210 days ago
visibility:
secret

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!