搜索
查看: 21|回复: 0

vgjkhyk

[复制链接]
 楼主| 发表于 2018-12-2 17:20:43 | 显示全部楼层 |阅读模式
  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. void dfs2(int u)
  24. {
  25.     if(book[u]==1) return;
  26.     book[u]=1;
  27.     cnt++;
  28.     num[cnt]=u;
  29.     //printf("%d ",u)P
  30.     for(int i=0;i<e[u].size();i++)
  31.     {
  32.         int v;
  33.         v=e[u][i];
  34.         if(!(u==neverP && v==neverQ) && !(v==neverP && u==neverQ))
  35.             dfs2(v);
  36.         
  37.     }
  38.     return ;
  39. }

  40. int main()
  41. {
  42.     //memset(ans,0x3F,sizeof(ans));
  43.     cin >> n >> m;
  44.     for(int i=1;i<=m;i++)
  45.     {
  46.         int x,y;
  47.         cin >> x >> y;
  48.         e[x].push_back(y);
  49.         e[y].push_back(x);
  50.         p[i]=x;
  51.         q[i]=y;
  52.     }
  53.     //sort 使其所有的点从小到大
  54.     for(int i=1;i<=n;i++)
  55.     {
  56.         sort(e[i].begin(),e[i].end());
  57.     }
  58.     if(m==n-1)
  59.     {
  60.         dfs(1);
  61.         for(int k=1;k<=n;k++)
  62.             printf("%d ",num[k]);
  63.     }
  64.     else
  65.     {
  66.         for(int i=1;i<=m;i++)
  67.         {
  68.             memset(book,0,sizeof(book));
  69.             memset(num,0,sizeof(num));
  70.             cnt=0;
  71.             neverP=p[i];neverQ=q[i];
  72.             dfs2(1);
  73.             if(cnt==n)
  74.             {
  75.                 if(ans[1]==0)
  76.                 {
  77.                     for(int j=1;j<=n;j++)
  78.                     {
  79.                         ans[j]=num[j];
  80.                     }
  81.                 }
  82.                 else
  83.                 {
  84.                     //字典
  85.                     //num 1 3 2 4 5 6
  86.                     //ans 1 3 2 5 4 6
  87.                     for(int j=1;j<=n;j++)
  88.                     {
  89.                         if(ans[j]==num[j])
  90.                             continue;
  91.                         else if (num[j]>ans[j])
  92.                             break;
  93.                         else if(num[j]<ans[j])
  94.                         {
  95.                             for(int k=1;k<=n;k++)
  96.                             {
  97.                                 ans[k]=num[k];
  98.                             }
  99.                             for(int k=1;k<=n;k++)
  100.                                 printf("%d ",ans[k]);
  101.                             printf("\n");
  102.                             break;
  103.                         }
  104.                     }
  105.                 }
  106.             }
  107.         }
  108.         /*
  109.         for(int k=1;k<=n;k++)
  110.             printf("%d ",ans[k]);
  111.         */
  112.     }
  113.     return 0;
  114. }
复制代码


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

广播台
特别关注
快速回复 返回顶部 返回列表