拓扑排序+DFS（POJ1270）

【日后练手】（非解题）

拓扑排序+DFS（POJ1270）

#include<stdio.h>

#include<iostream>

#include<cstdio>

#include<queue>

#include <vector>

#include<map>

#include<stack>

#include<cmath>

#include<cstring>

#include<cstdlib>

#include<climits>

#include<algorithm>

using namespace std;

#define LL long long

#define PI acos(-1.0)

#define ING 0x7fffffff

#define INF 0x3f3f3f3f

#define DA 100005

#define N 1010

bool ma[40][40];

int pre[40];

map<char,int>gg;

int rsk;

char ans[40];

char da[30];

void tuopu(int sum)

{

    if(sum==rsk)

    {

        printf("%s\n",ans);

        return;

    }

    for(int i=0;i<rsk;i++)

    {

        if(pre[i]==0)

        {

            pre[i]--;

            ans[sum]=da[i];

            for(int j=0;j<rsk;j++)

            {

                if(ma[i][j])

                {

                    pre[j]--;

                }

            }

            tuopu(sum+1);

            pre[i]++;

            for(int j=0;j<rsk;j++)

            {

                if(ma[i][j])

                    pre[j]++;

            }

        }

    }

}

int main()

{

    char c;

    char s1[55];

    char s[55];

    while(gets(s1))

    {

        int flat=0;

        int lg=strlen(s1);

        int num=0;

        for(int i=0;i<lg;i++)

        {

            if(s1[i]>='a'&&s1[i]<='z')

                da[num++]=s1[i];

        }

       // da[num]='\0';

        rsk=num;

        sort(da,da+num);

        for(int i=0;i<num;i++)

            gg[da[i]]=i;

        gets(s);

        int len=strlen(s);

        int j1,j2;

        memset(pre,0,sizeof(pre));

        memset(ma,0,sizeof(ma));

        for(int i=0;i<len;i++)

        {

            if(s[i]>='a'&&s[i]<='z')

            {

                if(flat==0)

                {

                    j1=s[i];

                    flat=1;

                }

                else

                {

                    j2=s[i];

                    ma[gg[j1]][gg[j2]]=1;

                    pre[gg[j2]]++;

                    flat=0;

                }

            }

        }

        memset(ans,0,sizeof(ans));

        tuopu(0);

        printf("\n");

    }

    return 0;

}

拓扑排序+DFS（POJ1270）的相关教程结束。