fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define el '\n'
  5. #define all(v) v.begin() , v.end() 
  6. #define ull unsigned long long 
  7. #define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
  8. #define loop(n) for(int i=0; i<n; i++)
  9. #define int ll
  10. #define DAVIDs signed
  11. const int dx[]={1,-1, 0, 0, 1, 1,-1,-1};
  12. const int dy[]={0, 0, 1,-1, 1,-1,-1, 1};
  13. const int N = 1e5+5;
  14. const int MOD = 1e9 + 7;
  15. #define mod %MOD
  16. istream& operator>>(istream& in, vector<int>& v){
  17.   for(auto& it: v) in >> it;
  18.   return in;
  19. }
  20. ostream& operator<<(ostream& out, vector<int>&v){
  21.   for(auto& it: v) out << it << ' ';
  22.   return out ;
  23. }
  24.  
  25. void solve(){
  26.   int n; cin>>n;
  27.   vector<pair<int,int>>adj[n+1];
  28.   for(int i=1; i<n; i++){
  29.     int a,b,c; cin>>a>>b>>c;
  30.     adj[a].push_back({b,c-1});
  31.     adj[b].push_back({a,c-1});
  32.   }
  33.   queue<int>q;
  34.   vector<int>dist(n+1,1e9);
  35.   vector<int>leafs;
  36.   vector<int>par(n+1,-1);
  37.   q.push(1);
  38.   dist[1]=0;
  39.   while(!q.empty()){
  40.     int node = q.front();
  41.     q.pop();
  42.     bool leaf = 1;
  43.     for(auto [ch,co]: adj[node]){
  44.       if(dist[ch]>dist[node]+1){
  45.         dist[ch]=dist[node]+1;
  46.         leaf=0;
  47.         par[ch]=node;
  48.         q.push(ch);
  49.       }
  50.     }
  51.     if(leaf)leafs.push_back(node);
  52.   }
  53.   function<bool(int)>trouble=[&](int node){
  54.     while(node!=-1){
  55.       int parent=par[node];
  56.       for(auto &[ch,co]:adj[node]){
  57.         if(ch==parent && co)return 1;
  58.       }
  59.       node=parent;
  60.     }
  61.     return 0;
  62.   };
  63.   vector<int>res;
  64.   for(auto leaf:leafs){
  65.     if(trouble(leaf)){
  66.       int cur = leaf;
  67.       while(cur!=-1){
  68.         for(auto &[ch,co]:adj[cur]){
  69.           if(ch==par[cur])co=0;
  70.         }
  71.         if(par[cur]!=-1){
  72.           for(auto &[ch,co]:adj[par[cur]]){
  73.             if(ch==cur)co=0;
  74.           }
  75.         }
  76.         cur=par[cur];
  77.       }
  78.       res.push_back(leaf);
  79.     }
  80.   }
  81.   cout<<res.size()<<el;
  82.   cout<<res;
  83. }
  84. DAVIDs main() {
  85.   fast;
  86.   int t=1;
  87.   // cin>>t;
  88.   while(t--)solve();
  89.   return 0;
  90. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
5
1 2 2
2 3 2
3 4 2
4 5 2
stdout
copy 
1
5
https://ideone.com/uyqvBH
language:
C++ (gcc 8.3)
created:
223 days 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!