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

2020-11-19 11:33

阅读:911

标签:拓扑排序   dfs   

大致题意:每个样例包含两行,第一行输入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 = ‘a‘ && t 






poj 1270 Following Orders(拓扑排序+dfs),搜素材,soscw.com

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

标签:拓扑排序   dfs   

原文地址:http://blog.csdn.net/u013081425/article/details/24938629


评论


亲,登录后才可以留言!