fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. const int N = 500067;
  5.  
  6. vector<pair<int, int>> adj[N]; 
  7. int color[N];
  8. bool czy[N];
  9. bool czy_krawedz[N];
  10. vector<int> na;
  11. vector<int> sa;
  12.  
  13. void dfs(int n, int b, int p_edge){
  14.     czy[n] = true;
  15.     color[n] = b;
  16.  
  17.     for(auto& p : adj[n]) {
  18.         int o = p.first;
  19.         int id = p.second;
  20.  
  21.         if(id == p_edge) continue;
  22.  
  23.         if(czy[o]) {
  24.             if(!czy_krawedz[id]) {
  25.                 czy_krawedz[id] = true;
  26.                 na.push_back(id);
  27.             }
  28.         } else {
  29.             czy_krawedz[id] = true;
  30.             dfs(o, b, id);
  31.         }
  32.     }
  33. }
  34.  
  35. int main() {
  36. 	ios_base::sync_with_stdio          (0);
  37. 	cin.tie(0);
  38. 	int a, k,               n;
  39. 	cin            >>           n;
  40.  
  41. 	for(int i = 1;                      i < n; i++){
  42. 		cin >> a                    >> k;
  43. 		adj[a].push_back({k, i});
  44. 		adj[k].push_back({a, i});
  45. 	}
  46.  
  47. 	int licznik = 0;
  48. 	for(int i = 1; i <= n; i++){
  49. 		if(!czy[i]){
  50. 			licznik++;
  51. 			sa.push_back(i);
  52. 			dfs(i, licznik, 0);
  53. 		}
  54. 	}
  55.  
  56. 	licznik--;
  57. 	cout<<licznik<<         endl;
  58.  
  59. 	for(int i = 0; i <    licznik; i++){
  60. 	    cout << na[i] << " " << sa[0] << " " <<       sa[i + 1] <<endl;
  61. 	}
  62.  
  63. 	return 0;
  64. }
Success #stdin #stdout 0.01s 16764KB
comments (?)
stdin
copy 
7
1 2
2 3
3 4
1 4
2 4
6 5
stdout
copy 
2
4 1 5
5 1 7
https://ideone.com/6Zt9yJ
language:
C++14 (gcc 8.3)
created:
1 day 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!