Codeforces Testing Round #5 B DFS

 #include <iostream>   
#include <cstdio>   
#include <cmath>   
#include <cstdlib>   
#include <string>   
#include <cstring>   
#include <algorithm>   
#include <iomanip>   
#include <set>   
  
using namespace std;  
const int inf = 0x7fffffff;  
const int maxn = 10000;  
  
int x[105],y[105];  
int fw[10][10];  
int a[105],b[105];  
int k[10];  
int mj,t;  
  
void DFS(int x){  
    for(int i=0;i<=6;++i)  
        if(fw[x][i]>0){  
            fw[x][i]--;  
            fw[i][x]--;  
            //cout<<i<<"----"<<endl;   
            DFS(i);  
            //cout<<i<<"----"<<endl;   
            t++;  
            a[t]=x, b[t]=i;           //緩存結果   
        }  
}  
  
int main(){  
    int n;  
    while(cin>>n){  
        memset(fw,0,sizeof(fw));  
        for(int i=1;i<=n;++i){  
            cin>>x[i]>>y[i];  
            fw[x[i]][y[i]]++; fw[y[i]][x[i]]++;   //存在的雙向邊   
            k[x[i]]++; k[y[i]]++;                 //記下數據   
        }  
  
        //cout<<fw[5][5]<<endl;   
  
        mj=x[1],t=0;  
        for(int i=0;i<=6;++i)  
            if(k[i]%2) mj=i,t++;  
        if(t!=2&&t!=0){   //出現的數字為奇數次的數有奇數個,不可能   
            puts("No solution");  
            continue;  
        }  
        t=0;  
          
        DFS(mj);  //從出現奇數次的數字開始搜   
  
        //cout<<t<< ' ' <<n<<endl;   
  
        if(t<n){         // 沒有把所有的邊都用上, 所以不可能   
            puts("No solution");  
            continue;  
        }  
        for(int i=t;i>=1;--i){  
            for(int j=1;j<=n;++j)  
                if(a[i]==x[j]&&b[i]==y[j]){      // 與數據同向   
                    cout<<j<<' '<<'+'<<endl;  
                    x[j]=10;    // 用過了捨去   
                    break;  
                }  
                else if(a[i]==y[j]&&b[i]==x[j]){  // 與數據反向   
                    cout<<j<<' '<<'-'<<endl;  
                    x[j]=10;   // 用過了捨去   
                    break;  
                }  
        }  
    }  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <set>

using namespace std;
const int inf = 0x7fffffff;
const int maxn = 10000;

int x[105],y[105];
int fw[10][10];
int a[105],b[105];
int k[10];
int mj,t;

void DFS(int x){
    for(int i=0;i<=6;++i)
        if(fw[x][i]>0){
            fw[x][i]--;
            fw[i][x]--;
            //cout<<i<<"----"<<endl;
            DFS(i);
            //cout<<i<<"----"<<endl;
            t++;
            a[t]=x, b[t]=i;           //緩存結果
        }
}

int main(){
    int n;
    while(cin>>n){
        memset(fw,0,sizeof(fw));
        for(int i=1;i<=n;++i){
            cin>>x[i]>>y[i];
            fw[x[i]][y[i]]++; fw[y[i]][x[i]]++;   //存在的雙向邊
            k[x[i]]++; k[y[i]]++;                 //記下數據
        }

        //cout<<fw[5][5]<<endl;

        mj=x[1],t=0;
        for(int i=0;i<=6;++i)
            if(k[i]%2) mj=i,t++;
        if(t!=2&&t!=0){   //出現的數字為奇數次的數有奇數個,不可能
            puts("No solution");
            continue;
        }
        t=0;
        
        DFS(mj);  //從出現奇數次的數字開始搜

        //cout<<t<< ' ' <<n<<endl;

        if(t<n){         // 沒有把所有的邊都用上, 所以不可能
            puts("No solution");
            continue;
        }
        for(int i=t;i>=1;--i){
            for(int j=1;j<=n;++j)
                if(a[i]==x[j]&&b[i]==y[j]){      // 與數據同向
                    cout<<j<<' '<<'+'<<endl;
                    x[j]=10;    // 用過了捨去
                    break;
                }
                else if(a[i]==y[j]&&b[i]==x[j]){  // 與數據反向
                    cout<<j<<' '<<'-'<<endl;
                    x[j]=10;   // 用過了捨去
                    break;
                }
        }
    }
    return 0;
}