vgjkhyk

渣男.

1. #include <cstdio>
   
2. #include <iostream>
   
3. #include <cstring>
   
4. #include <vector>
   
5. #include <algorithm>
   
6. using namespace std;
   
7. vector<int> e[5001];
   
8. int n,m,book[5001]={0},num[5001],p[5001],q[5001],ans[50001]={0};
   
9. int cnt=0,neverP,neverQ;
   
10. void dfs(int u)
    
11. {
    
12.     if(book[u]==1) return;
    
13.     book[u]=1;
    
14.     cnt++;
    
15.     num[cnt]=u;
    
16.     //printf("%d ",u);
    
17.     for(int i=0;i<e[u].size();i++)
    
18.     {
    
19.         dfs(e[u][i]);
    
20.     }
    
21.     return ;
    
22. }
    
23. 
    
24. void dfs2(int u)
    
25. {
    
26.     if(book[u]==1) return;
    
27.     book[u]=1;
    
28.     cnt++;
    
29.     num[cnt]=u;
    
30.     //printf("%d ",u)P
    
31.     for(int i=0;i<e[u].size();i++)
    
32.     {
    
33.         int v;
    
34.         v=e[u][i];
    
35.         if(!(u==neverP && v==neverQ) && !(v==neverP && u==neverQ))
    
36.             dfs2(v);
    
37.         
    
38.     }
    
39.     return ;
    
40. }
    
41. 
    
42. int main()
    
43. {
    
44.     //memset(ans,0x3F,sizeof(ans));
    
45.     cin >> n >> m;
    
46.     for(int i=1;i<=m;i++)
    
47.     {
    
48.         int x,y;
    
49.         cin >> x >> y;
    
50.         e[x].push_back(y);
    
51.         e[y].push_back(x);
    
52.         p[i]=x;
    
53.         q[i]=y;
    
54.     }
    
55.     //sort 使其所有的点从小到大
    
56.     for(int i=1;i<=n;i++)
    
57.     {
    
58.         sort(e[i].begin(),e[i].end());
    
59.     }
    
60.     if(m==n-1)
    
61.     {
    
62.         dfs(1);
    
63.         for(int k=1;k<=n;k++)
    
64.             printf("%d ",num[k]);
    
65.     }
    
66.     else
    
67.     {
    
68.         for(int i=1;i<=m;i++)
    
69.         {
    
70.             memset(book,0,sizeof(book));
    
71.             memset(num,0,sizeof(num));
    
72.             cnt=0;
    
73.             neverP=p[i];neverQ=q[i];
    
74.             dfs2(1);
    
75.             if(cnt==n)
    
76.             {
    
77.                 if(ans[1]==0)
    
78.                 {
    
79.                     for(int j=1;j<=n;j++)
    
80.                     {
    
81.                         ans[j]=num[j];
    
82.                     }
    
83.                 }
    
84.                 else
    
85.                 {
    
86.                     //字典
    
87.                     //num 1 3 2 4 5 6
    
88.                     //ans 1 3 2 5 4 6
    
89.                     for(int j=1;j<=n;j++)
    
90.                     {
    
91.                         if(ans[j]==num[j])
    
92.                             continue;
    
93.                         else if (num[j]>ans[j])
    
94.                             break;
    
95.                         else if(num[j]<ans[j])
    
96.                         {
    
97.                             for(int k=1;k<=n;k++)
    
98.                             {
    
99.                                 ans[k]=num[k];
    
100.                             }
     
101.                             for(int k=1;k<=n;k++)
     
102.                                 printf("%d ",ans[k]);
     
103.                             printf("\n");
     
104.                             break;
     
105.                         }
     
106.                     }
     
107.                 }
     
108.             }
     
109.         }
     
110.         /*
     
111.         for(int k=1;k<=n;k++)
     
112.             printf("%d ",ans[k]);
     
113.         */
     
114.     }
     
115.     return 0;
     
116. }
     

复制代码