POJ1270 Following Orders {图论}【拓扑排序】

题意

    第一列给出所有的字母数，第二列给出先后顺序。然后按字典序最小的方式输出所有的可能性。此题为拓扑排序，并且运用到了$dfs$回溯。     两种方法。 二维数组建图

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