首页 > 代码库 > 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 欧拉路