sgu 101. Domino 夜

http://acm.sgu.ru/problem.php?contest=0&problem=101

要想有解  首先必须是一个联通图

而且度为奇数的点的个数要么为0要么为2 否则无解

有解dfs搜一下就可以 不过如果存在度为奇数的点 要从度为奇数的点开始搜

搜的时候需要记录边 用栈记录 注意入栈顺序

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>

#define ll long long

using namespace std;
const int N=7;
const int M=10005;
int head[N],I;
struct node
{
	int j,next;
	int k;
}edge[M];
int num[N],f[N];
bool visited[M];
stack<int>st;
int fx(int x)
{
    if(f[x]!=x)
    f[x]=fx(f[x]);
    return f[x];
}
void add(int i,int j,int k)
{
	edge[I].j=j;
	edge[I].k=k;
	edge[I].next=head[i];
	head[i]=I++;
}
void dfs(int x)
{
	visited[x]=true;
	visited[x^1]=true;
	for(int t=head[edge[x].j];t!=-1;t=edge[t].next)
	{
		if(!visited[t])
		{
			dfs(t);
		}
	}
	st.push(edge[x].k);
}
int main()
{
    //freopen("data.in","r",stdin);
	int n;
	while(cin>>n)
	{
	    while(!st.empty()) st.pop();
		memset(num,0,sizeof(num));
		memset(head,-1,sizeof(head));I=0;
		for(int i=0;i<N;++i)
		f[i]=i;
		int root;
		for(int i=1;i<=n;++i)
		{
			int l,r;
			cin>>l>>r;
			f[fx(l)]=fx(r);
			add(l,r,i);
			add(r,l,-i);
			++num[l];++num[r];
			root=r;
		}
		vector<int>vt;
		for(int i=0;i<N;++i)
		if(num[i]>0)
		vt.push_back(i);
		int odd=0;
		for(unsigned int i=0;i<vt.size();++i)
		{
		    if(num[vt[i]]%2==1) {root=vt[i];++odd;}
		    if(i>0&&f[vt[i]]!=f[vt[i-1]]){odd=1;break;}
		}
		if(odd!=0&&odd!=2)
        {cout<<"No solution"<<endl;}
		else
		{
		    memset(visited,false,sizeof(visited));
            for(int t=head[root];t!=-1;t=edge[t].next)
            if(!visited[t])
            dfs(t);
			while(!st.empty())
			{
				int k=st.top();st.pop();
				cout<<abs(k)<<" ";
				if(k>0)cout<<"+"<<endl;
				else cout<<"-"<<endl;
			}
		}

	}
	return 0;
}