首页 > 代码库 > 欧拉图 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第六次 送货
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。