fork(1) download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=1000000+10;
  27.  
  28. int n;
  29. int begin[MAX],next[MAX],t[MAX],tot,ne[MAX];
  30.  
  31. void add(int a,int b)
  32. {
  33.     t[++tot]=b;
  34.     next[tot]=begin[a];
  35.     begin[a]=tot;
  36. }
  37.  
  38. int hash[MAX],fa[MAX];
  39. int q[MAX],head,end;
  40.  
  41. void BFS()
  42. {
  43.     head=1,end=1;
  44.     q[end++]=1;
  45.     hash[1]=1;
  46.     while(head<end)
  47.     {
  48.         int u=q[head++];
  49.         for(int i=begin[u];i;i=next[i])
  50.         {
  51.             int v=t[i];
  52.             if(!hash[v])
  53.             {
  54.                 hash[v]=1;
  55.                 fa[v]=u;
  56.                 q[end++]=v;
  57.             }
  58.         }
  59.     }
  60. }
  61.  
  62. //如果一棵子树能够先访问根，则反过来必定能最后访问根。。
  63. int could[MAX];
  64.  
  65. void fail()
  66. {
  67.     printf("BRAK\n");
  68.     exit(0);
  69. }
  70. void work(int u)
  71. {
  72.     int i;
  73.     int must=0;
  74.     could[u]=1;
  75.     for(i=begin[u];i;i=next[i])
  76.     {
  77.         int v=t[i];
  78.         if(v==fa[u])
  79.             continue;
  80.         if(next[ begin[v] ])
  81.             ++must;
  82.         if(!could[v])
  83.             must=2;
  84.     }
  85.     if(must>1)
  86.         could[u]=0;
  87. }
  88.  
  89. int is[MAX];
  90. int dp0[MAX],dp1[MAX],ans[MAX];
  91.  
  92. void show(int u)
  93. {
  94.     int i;
  95.     vector<int> go,go1;
  96.     for(i=begin[u];i;i=next[i])
  97.     {
  98.         int v=t[i];
  99.         if(v==fa[u])
  100.             continue;
  101.         if(next[begin[v]])
  102.             go.pb(v);
  103.         else go1.pb(v);
  104.     }
  105.     if(go.size())
  106.         ans[go[0]]=ans[u]^1;
  107.     if(ans[u]==0)
  108.     {
  109.         printf("%d\n",u);
  110.         if(go.size())
  111.             show(go[0]);
  112.     }
  113.     REP2(i,0,(int)go1.size())
  114.         printf("%d\n",go1[i]);
  115.     if(ans[u]==1)
  116.     {
  117.         if(go.size())
  118.             show(go[0]);
  119.         printf("%d\n",u);
  120.     }
  121. }
  122.  
  123. int main()
  124. {
  125. #ifndef ONLINE_JUDGE
  126. //    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  127. #endif
  128.     int i;
  129.     scanf("%d",&n);
  130.     REP(i,1,n-1)
  131.     {
  132.         int a,b;
  133.         scanf("%d%d",&a,&b);
  134.         add(a,b);
  135.         add(b,a);
  136.     }
  137.     BFS();
  138.     for(i=n;i>=1;--i)
  139.     {
  140.         int t=q[i];
  141.         work(t);
  142.     }
  143.     int u=n;
  144.     while(1)
  145.     {
  146.         is[u]=1;
  147.         if(u==1)
  148.             break;
  149.         u=fa[u];
  150.     }
  151.     if(could[n])//不先跳到这个点。。
  152.         dp1[n]=1;
  153.     if(!next[ begin[n] ])
  154.         dp0[n]=1;
  155.     u=fa[n];
  156.     int last=n;
  157.     ne[u]=n;
  158.     while(1)
  159.     {
  160.         int go=0,go1=0;
  161.         for(i=begin[u];i;i=next[i])
  162.         {
  163.             int v=t[i];
  164.             if(is[v])
  165.                 continue;
  166.             if(!could[v])
  167.                 fail();
  168.             if(next[begin[v]])
  169.                 ++go;
  170.             else ++go1;
  171.         }
  172.         if(go>2)
  173.             fail();
  174.         if(go==0)
  175.         {
  176.             dp0[u]=(go1?dp0[last]:(dp0[last] || dp1[last]));
  177.             dp1[u]=dp0[last] || dp1[last];
  178.         }
  179.         if(go==1)
  180.         {
  181.             dp0[u]=dp0[last];
  182.             dp1[u]=dp0[last] || dp1[last];
  183.         }
  184.         if(go==2)
  185.         {
  186.             dp0[u]=0;
  187.             dp1[u]=dp0[last];
  188.         }
  189.         if(u==1)
  190.             break;
  191.         last=u;
  192.         u=fa[u];
  193.         ne[u]=last;
  194.     }
  195.     if(!dp0[1])
  196.         fail();
  197.     u=1;
  198.     ans[1]=0;
  199.     while(1)
  200.     {
  201.         vector<int> go,go1;
  202.         for(i=begin[u];i;i=next[i])
  203.         {
  204.             int v=t[i];
  205.             if(is[v])
  206.                 continue;
  207.             if(!next[begin[v]])
  208.                 go1.pb(v);
  209.             else
  210.                 go.pb(v);
  211.         }
  212.         int tt=ne[u];
  213.         if(ans[u]==0)
  214.         {
  215.             printf("%d\n",u);
  216.             if(!go1.size() && !go.size())
  217.             {
  218.                 if(dp1[tt])
  219.                     ans[tt]=1;
  220.                 else ans[tt]=0;
  221.             }
  222.             else
  223.             {
  224.                 if(go.size())
  225.                 {
  226.                     ans[go[0]]=1;
  227.                     show(go[0]);
  228.                 }
  229.                 REP2(i,0,(int)go1.size())
  230.                     printf("%d\n",go1[i]);
  231.                 ans[tt]=0;
  232.             }
  233.         }
  234.         else
  235.         {
  236.             REP2(i,0,(int)go1.size())
  237.                 printf("%d\n",go1[i]);
  238.             if(go.size())
  239.             {
  240.                 ans[go[0]]=0;
  241.                 show(go[0]);
  242.             }
  243.             printf("%d\n",u);
  244.             if(go.size()<2)
  245.             {
  246.                 if(dp1[tt])
  247.                     ans[tt]=1;
  248.                 else ans[tt]=0;
  249.             }
  250.             else
  251.             {
  252.                 ans[go[1]]=1;
  253.                 show(go[1]);
  254.                 ans[tt]=0;
  255.             }
  256.         }
  257.         if(u==n)
  258.             break;
  259.         u=tt;
  260.     }
  261.     return 0;
  262. }
  263.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
30
1 27
27 4
4 14
14 28
28 2
2 13
13 25
25 11
11 30
1 7
7 24
14 18
18 10
14 8
8 26
13 15
15 3
30 5
5 29
24 17
10 12
12 20
17 22
26 9
20 23
23 6
17 21
1 19
23 16
compilation info 
Traceback (most recent call last):
  File "/usr/lib/python3.2/py_compile.py", line 119, in compile
    optimize=optimize)
  File "./prog.py", line 21
    using namespace std;
                  ^
SyntaxError: invalid syntax

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/lib/python3.2/py_compile.py", line 123, in compile
    raise py_exc
py_compile.PyCompileError:   File "./prog.py", line 21
    using namespace std;
                  ^
SyntaxError: invalid syntax
stdout
copy 
Standard output is empty
https://ideone.com/JrXuzy
language:
Python 3 (python  3.9.5)
created:
10 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!