fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. #include<functional>
  5. #include<set>
  6. using namespace std;
  7.  
  8.  
  9. vector<vector<int>> adj;
  10. vector<int> par;
  11. vector<bool> deleted;
  12. vector<int> depth;
  13. priority_queue<pair<int, int>> leaves;
  14.  
  15. void dfs(int u, int p=-1, int d=0){
  16.     if(par[u] != -1) return;
  17.     par[u] = p;
  18.     depth[u] = d;
  19.     if(adj[u].size() == 1) leaves.push(make_pair(depth[u], u));
  20.     for(auto v: adj[u]) dfs(v, u, d+1);
  21. }
  22.  
  23. bool delete_dfs(int u){
  24.     if(deleted[u]) return 0;
  25.     deleted[u] = true;
  26.     for(auto v: adj[u]){
  27.         if(par[u] != v) delete_dfs(v);
  28.     } 
  29.     return par[u]!=0;
  30. }
  31.  
  32. int main()
  33. {
  34.     int n; cin >> n;
  35.     adj.assign(n, vector<int>());
  36.     par.assign(n, -1);
  37.     deleted.assign(n, 0);
  38.     depth.assign(n, 0);
  39.  
  40.     for(int i=0; i<n-1 ;i ++){
  41.         int u, v; cin >> u >> v;
  42.         u--; v--;
  43.         adj[u].push_back(v);
  44.         adj[v].push_back(u);
  45.     }
  46.  
  47.     dfs(0, 0);
  48.     long long res = 0;
  49.     while(!leaves.empty()){
  50.         auto leave_p = leaves.top(); leaves.pop();
  51.         int leave = leave_p.second;
  52.         if(leave_p.first != depth[leave] || deleted[leave]) continue;
  53.         bool aux = delete_dfs(par[leave]); res+=aux;
  54.         cout << leave+1 << " " << leave_p.first << " " <<depth[leave] <<  endl;
  55.         for(int i=0; i<n; i++){
  56.             if(!deleted[i]) cout << i+1 << endl;
  57.         }
  58.         cout <<endl;
  59.         if(!aux) continue;
  60.         deleted[par[par[leave]]] = true;
  61.     }
  62.  
  63.     cout << res <<  endl;
  64.     return 0;
  65. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
7
1 2
2 3
2 4
4 5
4 6
5 7
stdout
copy 
7 4 4
1
2
3
4
6

6 3 3
1
2
3
6

3 2 2
1
6

1 0 0
6

1
https://ideone.com/EZQm1m
language:
C++14 (gcc 8.3)
created:
13 hours 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!