博客

题意

第一列给出所有的字母数，第二列给出先后顺序。然后按字典序最小的方式输出所有的可能性。此题为拓扑排序，并且运用到了



d

f

s

dfs






d


f


s





回溯。

两种方法。


二维数组建图

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, NN = 1e3 + 10, INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;
char str[N], compare[N];
int sum, num_edge;
int a[N], indegree[N], head[N];
map<char, int> mp;
int edge[NN][NN];
char ans[N];
void topo(int depth) {
    if (depth == sum) {
        printf("%s\n", ans);
        return;
    }
    for (int i = 0; i < sum; i++) {
        if (indegree[i] == 0) {
            --indegree[i];
            ans[depth] = a[i];
            for (int j = 0; j < sum; j++)
                if (edge[i][j])
                    --indegree[j];
            topo(depth + 1);
            ++indegree[i];
            for (int j = 0; j < sum; j++)
                if (edge[i][j])
                    ++indegree[j];
        }
    }
}
void init() {
    sum = 0;
    memset(indegree, 0, sizeof indegree);
    memset(edge, 0, sizeof edge);
    memset(ans, 0, sizeof ans);
    mp.clear();
}
int main() {
    while (gets(str) != NULL) {
        init();
        for (int i = 0; i < strlen(str); i++)
            if (str[i] >= 'a' && str[i] <= 'z')
                a[sum++] = str[i];
        sort(a, a + sum);
        for (int i = 0; i < sum; i++)
            mp[a[i]] = i;
        gets(compare);
        int temp1, temp2;
        bool flag = true;
        for (int i = 0; i < strlen(compare); i++) {
            if (compare[i] >= 'a' && compare[i] <= 'z') {
                if (flag) {
                    temp1 = compare[i];
                    flag = false;
                } else {
                    temp2 = compare[i];
                    indegree[mp[temp2]]++;
                    edge[mp[temp1]][mp[temp2]] = 1;
                    flag = true;
                }
            }
        }
        topo(0);
        printf("\n");
    }
    return 0;
}

链式前向星建图

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, NN = 1e3 + 10, INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;
char str[N], compare[N];
int sum, num_edge;
int a[N], indegree[N], head[N];
map<char, int> mp;
char ans[N];
struct Edge {
    int next;
    int to;
} edge[N];
void add_edge(int from, int to) {
    num_edge++;
    edge[num_edge].next = head[from];
    edge[num_edge].to = to;
    head[from] = num_edge;
}
void topo(int depth) {
    if (depth == sum) {
        printf("%s\n", ans);
        return;
    }
    for (int i = 0; i < sum; i++) {
        if (indegree[i] == 0) {
            --indegree[i];
            ans[depth] = a[i];
            for (int j = head[i]; j != -1; j = edge[j].next)
                --indegree[edge[j].to];
            topo(depth + 1);
            ++indegree[i];
            for (int j = head[i]; j != -1; j = edge[j].next)
                ++indegree[edge[j].to];
        }
    }
}
void init() {
    sum = 0;
    num_edge = 0;
    memset(indegree, 0, sizeof indegree);
    memset(edge, 0, sizeof edge);
    memset(ans, 0, sizeof ans);
    memset(head, -1, sizeof head);
    mp.clear();
}
int main() {
    while (gets(str) != NULL) {
        init();
        for (int i = 0; i < strlen(str); i++)
            if (str[i] >= 'a' && str[i] <= 'z')
                a[sum++] = str[i];
        sort(a, a + sum);
        for (int i = 0; i < sum; i++)
            mp[a[i]] = i;
        gets(compare);
        int temp1, temp2;
        bool flag = true;
        for (int i = 0; i < strlen(compare); i++) {
            if (compare[i] >= 'a' && compare[i] <= 'z') {
                if (flag) {
                    temp1 = compare[i];
                    flag = false;
                } else {
                    temp2 = compare[i];
                    indegree[mp[temp2]]++;
                    add_edge(mp[temp1], mp[temp2]);
                    flag = true;
                }
            }
        }
        topo(0);
        printf("\n");
    }
    return 0;
}