首页 > 代码库 > 欧拉图 CCF2016第六次 送货

欧拉图 CCF2016第六次 送货

 1 // 欧拉图 CCF2016第六次 送货 2 // 思路: 3 // CCF数据很水。。。。这道题有问题 4 // 先判连通,再dfs边。 5 // 应为输出要满足字典序最小,用vector存图,sort一遍,用stack保存答案 6  7 #include <bits/stdc++.h> 8 using namespace std; 9 #define LL long long10 typedef pair<int,int> pii;11 const double inf = 123456789012345.0;12 const LL MOD =100000000LL;13 const int N =1e4+10;14 #define clc(a,b) memset(a,b,sizeof(a))15 const double eps = 1e-7;16 void fre() {freopen("in.txt","r",stdin);}17 void freout() {freopen("out.txt","w",stdout);}18 inline int read() {int x=0,f=1;char ch=getchar();while(ch>9||ch<0) {if(ch==-) f=-1; ch=getchar();}while(ch>=0&&ch<=9) {x=x*10+ch-0;ch=getchar();}return x*f;}19 20 vector<int> g[N];21 bool vit[N][N];22 bool vis[N];23 int d[N];24 void dfs(int x){25      vis[x]=true;26      for(int i=0;i<(int)g[x].size();i++){27         int v=g[x][i];28         if(!vis[v])29             dfs(v);30      }31 }32 stack<int> st;33 void euler(int x){34      for(int i=0;i<(int)g[x].size();i++){35         int v=g[x][i];36         if(!vit[x][v]){37             vit[x][v]=vit[v][x]=true;38             euler(v);39             st.push(v);40         }41      }42 }43 int main(){44     int n,m;45     scanf("%d%d",&n,&m);46     for(int i=1;i<=m;i++){47         int x,y;48         scanf("%d%d",&x,&y);49         g[x].push_back(y);50         g[y].push_back(x);51         d[x]++;d[y]++;52     }53     dfs(1);54     bool flag=true;55     for(int i=1;i<=n;i++){56         if(!vis[i]){57             flag=false;58             break;59         }60     }61     if(!flag){62         printf("-1\n");63     }64     else{65         int count=0;66         for(int i=1;i<=n;i++){67             sort(g[i].begin(),g[i].end());68             if(d[i]%2) count++;69         }70         if(count>2) printf("-1\n");71         else{72             printf("1");73             euler(1);74             while(!st.empty()){75                 int a=st.top();76                 st.pop();77                 printf(" %d",a);78             }79             printf("\n");80         }81     }82     return 0;83 }

 

欧拉图 CCF2016第六次 送货