程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1270 Following Orders(拓撲排序+dfs)

poj 1270 Following Orders(拓撲排序+dfs)

編輯：C++入門知識

大致題意：每個樣例包含兩行，第一行輸入n個字符，可能是無序的。第二行輸入成對的a b,代表a要在b前面。輸出所有的符合這樣的序列。

思路：很明顯的拓撲排序。要輸出所有的序列，那麼就從入度為0的點進行dfs，每次選擇一個入度為0的點，加入輸出序列並把與它相鄰的點的入度減一。dfs結束後要把狀態再改回來。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
using namespace std;

const int maxn = 110;

char contents[30];
bool mapp[60][60];
int n = 0;
char t,t1,t2;
int flag;
int in[30];
int vis[30];
int ans[30];

void dfs(int num)
{
    if(num == n)
    {
        for(int i = 0; i < n; i++)
            printf("%c",ans[i]);
        printf("\n");
        return;
    }

    for(int i = 0; i < n; i++)
    {
        if(!vis[i] && !in[ contents[i]-'a' ]) 
        {
            for(int j = 0; j < n; j++)
            {
                if(mapp[contents[i]-'a'][contents[j]-'a'])
                {
                    in[ contents[j]-'a']--;
                }
            }

            ans[num] = contents[i];
            vis[i] = 1;
            
            dfs(num+1);
            
            //注意將狀態更改回來
            for(int j = 0; j < n; j++)
            {
                if(mapp[contents[i]-'a'][contents[j]-'a'])
                {
                    in[ contents[j]-'a']++;
                }
            }
            vis[i] = 0;
        }
    }
}

int main()
{
    flag = 0;
    while(~scanf("%c",&t))
    {
        if(t >= 'a' && t <= 'z')
        {
            contents[n++] = t;
            continue;
        }
        else if(t == ' ') continue;
        else
        {
            if(flag)
                printf("\n");
            flag = 1;

            sort(contents,contents+n); //因為輸入可能是無序的，先排序
            memset(in,0,sizeof(in));
            memset(mapp,false,sizeof(mapp));
            memset(vis,0,sizeof(vis));

            while(~scanf("%c %c",&t1,&t2))
            {
                mapp[t1-'a'][t2-'a'] = 1;
                in[t2-'a']++;
                if(getchar() == '\n')
                    break;
            }
            
            dfs(0);
            n = 0;
        }
    }
    return 0;
}