SGU 101 Domino[오로라 경로]

제목 링크:
http://acm.sgu.ru/problem.php?contest=0&problem=101
제목:
N 개의 도미 노 골패,각 골패 의 좌우 양쪽 에 각각 0~6 의 정수(골패 가 회전 하여 좌우 두 수 를 바 꿀 수 있다)가 있 는데 이 골패 들 을 왼쪽 에서 오른쪽으로 배열 하 는 방안 을 구 해서 모든 인접 한 두 숫자 를 똑 같이 한다(즉,왼쪽 골패 오른쪽의 숫자 는 오른쪽 골패 왼쪽 의 숫자 와 같다).
분석:
숫자 를 점 으로 삼 고 골 패 를 가장자리 로 삼다.무방 향 도 를 구성 하고 오 라 의 길 을 구하 면 된다.오로라 경 로 를 구 하 는 데 도움 이 되 지 않 습 니 다.오로라 경로 깊이 설명:http://blog.chinaunix.net/uid-26380419-id-3164913.html
코드:

#include
#include
#include
#include
#include
using namespace std;
const int maxn = 200 + 5, maxm = 6 + 5;
struct Edge{
      int to;int dir; int id;int next;};
int tot = 0;
Edge edge[maxn];
stacks;
int pa[maxn], head[maxm], cnt[maxm];
bool vis[maxn];
int _find(int a)
{
    if(a == pa[a]) return a;
    return pa[a] = _find(pa[a]);
}
void unite(int a, int b)
{
    int ra = _find(a);
    int rb = _find(b);
    if(ra == rb) return ;
    pa[rb] = ra;
}
bool same(int a, int b)
{
    return _find(a) == _find(b);
}
void add_edge(int u, int v, int id)
{
    edge[tot].to = v;
    edge[tot].id = id;
    edge[tot].dir = 1;
    edge[tot].next = head[u];
    head[u] = tot++;
    edge[tot].to = u;
    edge[tot].dir = 0;
    edge[tot].id = id;
    edge[tot].next = head[v];
    head[v] = tot++;
}
void dfs(int u)
{
    for(int i = head[u]; i != -1; i = edge[i].next){
        if(!vis[i]){
            vis[i] = true;
            vis[i^1] = true;
            dfs(edge[i].to);
            s.push(edge[i]);
        }
    }
}
int main (void)
{
    int n ;cin>>n;
    memset(head, -1, sizeof(head));
    for(int i = 0; i <= 6; i++) pa[i] = i;
    int a, b;
    for(int i = 0; i < n; i++){
        cin>>a>>b;
        add_edge(a, b, i + 1);
        cnt[a]++;
        cnt[b]++;
        unite(a, b);
    }
    int be = -1;
    int ans = 0;
    for(int i = 0; i <= 6; i++){
        if(cnt[i] & 1){
            ans++;
            if(be == -1) be = i;
        }
    }
    if(ans != 0 && ans != 2) return cout<<"No solution"<0;
    for(int i = 0; i <= 6; i++){
        if(cnt[i] &&  be == -1) be = i;
        if(cnt[i] && !same(i, be)){
      return cout<<"No solution"<0;}
    }
    dfs(be);
    while(!s.empty()){
        Edge t = s.top();s.pop();
        cout<' ';
        if(t.dir == 0) cout<<"-"<else cout<<"+"<return 0;
}

다음으로 전송:https://www.cnblogs.com/Tuesdayzz/p/5758657.html