fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <unordered_map>
  6. #include <set>
  7. #include <array>
  8. using namespace std;
  9. #define SZ(a) (int)(a).size()
  10. typedef long long ll;
  11.  
  12. const auto lim = (int)1e5;
  13.  
  14. int main() {
  15. 	cin.sync_with_stdio(false);
  16. 	int n, m, nc;
  17. 	cin >> n >> m >> nc;
  18. 	vector<unordered_map<int, int>> al(n);
  19. 	for (auto i = 0; i < m; i++) {
  20. 		int u, v, c;
  21. 		cin >> u >> v >> c;
  22. 		u--; v--;
  23. 		al[u].emplace(v, c);
  24. 		al[v].emplace(u, c);
  25. 	}
  26. 	set<pair<int, int>> degs;
  27. 	for (auto u = 0; u < n; u++) {
  28. 		degs.emplace(SZ(al[u]), u);
  29. 	}
  30. 	auto ntri = 0;
  31. 	set<array<int, 3>> tris;
  32. 	for (auto i = 0; i < n; i++) {
  33. 		auto it = begin(degs);
  34. 		auto u = it->second;
  35. 		degs.erase(it);
  36. 		for (auto pv: al[u]) {
  37. 			auto v = pv.first;
  38. 			auto cuv = pv.second;
  39. 			for (auto pw: al[u]) {
  40. 				auto w = pw.first;
  41. 				if (v == w) {
  42. 					break;
  43. 				}
  44. 				auto cuw = pw.second;
  45. 				if (cuv == cuw) {
  46. 					continue;
  47. 				}
  48. 				auto it = al[v].find(w);
  49. 				if (it == end(al[v])) {
  50. 					continue;
  51. 				}
  52. 				auto cvw = it->second;
  53. 				if (cuv == cvw || cuw == cvw) {
  54. 					continue;
  55. 				}
  56. 				ntri++;
  57. 				if (ntri <= lim) {
  58. 					array<int, 3> tri = {u, v, w};
  59. 					sort(begin(tri), end(tri));
  60. 					tris.insert(tri);
  61. 				}
  62. 			}
  63. 		}
  64. 		for (auto pv: al[u]) {
  65. 			auto v = pv.first;
  66. 			degs.erase({SZ(al[v]), v});
  67. 			al[v].erase(u);
  68. 			degs.emplace(SZ(al[v]), v);
  69. 		}
  70. 	}
  71. 	printf("%d\n", ntri);
  72. 	if (ntri <= lim) {
  73. 		for (auto tri: tris) {
  74. 			for (auto i = 0; i < 3; i++) {
  75. 				printf("%d%c", tri[i]+1, " \n"[i == 2]);
  76. 			}
  77. 		}
  78. 	}
  79. 	return 0;
  80. }
  81.  
Runtime error #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/19iCaG
language:
C++14 (gcc 8.3)
created:
7 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!