pku 1270 Following Orders DFS+拓扑排序-蒲公英云

pku 1270 Following Orders DFS+拓扑排序

电玩女神 2022-08-09 14:52 147阅读 0赞

题意很清晰.

可以利用dfs遍历每一组值,然后加上剪枝条件.

由于剪枝可以利用当前节点和已遍历节点的顺序关系,可以使用拓扑排序.

注意: 输入的第一行不一定是有序的,我在这里sort了一下才过.

小结: 拓扑排序用于当序列中的元素有顺序关系时求可行的序列.

#include #include #include using namespace std; bool edge[26][26]; int inDegree[26]; char str[50]; char strTemp[250]; char ans[27]; int cnt; bool visited[26]; void dfs(int n) { if(n == cnt) { for(int i = 0; i < cnt; ++i) printf(“%c”, ans[i]); printf(“/n”); return; } for (int i = 0; i < cnt; ++i) { if(!visited[str[i]-‘a’] && !inDegree[str[i]-‘a’]) { visited[str[i]-‘a’] = true; for(int j = 0; j < cnt; ++j) if(edge[str[i]-‘a’][str[j]-‘a’]) inDegree[str[j]-‘a’]—; ans[n] = str[i]; dfs(n+1); visited[str[i]-‘a’] = false; for(int j = 0; j < cnt; ++j) if(edge[str[i]-‘a’][str[j]-‘a’]) inDegree[str[j]-‘a’]++; } } } int main() { while(cin.getline(str, 50)) { cnt = (strlen(str)+1)/2; for(int i = 0; i < cnt; ++i) str[i] = str[i*2]; str[cnt] = ‘/0’; sort(str, str+cnt); cin.getline(strTemp, 250); memset(edge, 0, sizeof(edge)); memset(visited, 0, sizeof(visited)); memset(inDegree, 0, sizeof(inDegree)); for(int i = 0; i < strlen(strTemp)+1; i+=4) { edge[strTemp[i]-‘a’][strTemp[i+2]-‘a’] = true; inDegree[strTemp[i+2]-‘a’]++; } dfs(0); printf(“/n”); } return 0; }