首页 > 代码库 > sgu101 欧拉路
sgu101 欧拉路
题意:给你n张牌,每个牌有两面,要求找出一种摆放顺序,使得相邻的牌的面相同。初始给出的牌的方向为正
#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <stack>#include <queue>#include <vector>#include <map>#include <string>#include <iostream>using namespace std;int father[7];int len;int head[7];int bx;int degree[7];int vis[7];int getfather(int x){ if(father[x]!=x) father[x]=getfather(father[x]); return father[x];}struct edge{ int val;int to;int next;int vis;int oppo;int t;}e[1111];void link(int a,int b){ int fa=getfather(a); int fb= getfather(b); father[fa]=fb;}void add(int from,int to,int val){ e[len].t=1; e[len].to =to ;e[len].val = val;e[len].vis=0; e[len].oppo= len+1; e[len].next= head[from]; head[from]= len++; e[len].to= from;e[len].val=val; e[len].t= 0; e[len].vis=0; e[len].oppo= len-1; e[len].next= head[to]; head[to]=len++;}int judge(){ bx= 0 ; int ans=0;int ans1=0; for(int i=0;i<=6;i++) if(vis[i])if(father[i]==i) ans++; if(ans!=1) return 0; for(int i=0;i<=6;i++) if(degree[i]&1) ans1++,bx= i; if(bx==0) for(int i=0;i<=6;i++) if(vis[i]) bx= i; if(ans1==2||ans1==0) return 1; return 0;}struct Node{ int t;int x;};stack <Node> q;void dfs(int x){ for(int i= head[x];i!=-1;i=e[i].next){ if(e[i].vis) continue; int cc=e[i].to; e[i].vis= 1;e[e[i].oppo].vis=1; dfs(cc); Node gg ; if(e[i].t==1) gg.t=1; else gg.t=0; gg.x= e[i].val; q.push(gg); }}int main(){ int n,a,b; scanf("%d",&n); memset(head,-1,sizeof(head)); len=0; memset(vis,0,sizeof(vis)); memset(degree,0,sizeof(degree)); for(int i=0;i<=6;i++) father[i]= i; for(int i=1;i<=n;i++){ scanf("%d%d",&a,&b); vis[a]=1;vis[b]=1; add(a,b,i); degree[a]++; degree[b]++; link(a,b); } if(judge()==0) printf("No solution\n"); else{ dfs(bx); while(!q.empty()){ Node t= q.top(); q.pop(); if(t.t==1) printf("%d +\n",t.x); else printf("%d -\n",t.x); } printf("\n"); } return 0;}
sgu101 欧拉路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。