fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  3. #define ll long long
  4. #define ld long double
  5. #define pb push_back
  6. using namespace std;
  7. const int m=2e5+1;
  8. vector<vector<int>>v;
  9. map<int,set<int>>inv;
  10. int vis[m],dp[m];
  11. void dfs(int node)
  12.      {
  13.        vis[node]=1;
  14.        for(auto child:v[node])
  15.        {
  16.            if(!vis[child])
  17.            {
  18.                dfs(child);
  19.                   dp[node]+=dp[child];
  20.                if(inv[node].count(child))
  21.                dp[node]++;
  22.            }
  23.        }
  24.      }
  25. void dfs1(int node)
  26. {
  27.     vis[node]=1;
  28.     int first=-1;
  29.     for(auto child:v[node])
  30.     {
  31.         if(vis[child])
  32.             first=child;
  33.     }
  34.         if(first!=-1)
  35.         {dp[node]=dp[first];
  36.             if(inv[first].count(node))
  37.                 dp[node]--;
  38.             else dp[node]++;
  39.         }
  40.     for(auto child:v[node])
  41.     {
  42.         if(!vis[child])
  43.         {
  44.             dfs1(child);
  45.         }
  46.     }
  47. }
  48. int main() {
  49.  fast
  50. int n,x,y;
  51. cin>>n;
  52. v.resize(n+1);
  53. for(int i=0;i<n-1;i++)
  54. {
  55.     cin>>x>>y;
  56.     v[x].pb(y);
  57.     v[y].pb(x);
  58.     inv[y].insert(x);
  59. }
  60. dfs(1);
  61. memset(vis,0,sizeof vis);
  62. dfs1(1);
  63. int mn=n;
  64. for(int i=1;i<=n;i++) mn=min(mn,dp[i]);
  65. vector<int>ans;
  66. for(int i=1;i<=n;i++)
  67. {
  68.     if(dp[i]==mn)
  69.         ans.pb(i);
  70. }
  71. sort(ans.begin(),ans.end());
  72. cout<<mn<<endl;
  73. for(auto i:ans) cout<<i<<" ";
  74.  return 0;
  75. }
Runtime error #stdin #stdout #stderr 0.01s 5520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_default_append
https://ideone.com/vchyg8
language:
C++ (gcc 8.3)
created:
2 years 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!