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;
}

补充：软件开发 , C++ ,

上一个：UVA 10344 23 out of 5(搜索+全排列)
下一个：C++ Data Member内存布局