网站源码建设模板,wordpress 搜索 高亮,安徽省住房和城乡建设厅网站领域,中国建设银行ie下载网站概念
一个有向无环图必然存在一个拓扑序列与之对应。
流程#xff1a;
先将所有入度为0的节点入队将队列中的节点出队#xff0c;出队序列就是对应拓扑序。对于弹出的节点x#xff0c;遍历x所有出度y#xff0c;对y进行入读减一操作检查入度减一之后的节点y#xff0c;…概念
一个有向无环图必然存在一个拓扑序列与之对应。
流程
先将所有入度为0的节点入队将队列中的节点出队出队序列就是对应拓扑序。对于弹出的节点x遍历x所有出度y对y进行入读减一操作检查入度减一之后的节点y如果入度为0再次将其入队循环流程2、3知道队列为空 以此图为例开始时节点1的入度为0将其入队而后节点2、3的入度均减一此时节点2的入度为0将其入队然后节点3、4的入度减一最后将节点3、4一次入队。 最终的拓扑排序结果是1、2、3、4
模板
给定一个 n 个点 m条边的有向图点的编号是 1到 n图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列如果拓扑序列不存在则输出 −1。
若一个由图中所有点构成的序列 A 满足对于图中的每条边 (x,y)x 在 A 中都出现在 y之前则称 A是该图的一个拓扑序列。
输入格式 第一行包含两个整数 n和m。
接下来 m行每行包含两个整数 x和y表示存在一条从点 x到点y的有向边(x,y)。
输出格式 共一行如果存在拓扑序列则输出任意一个合法的拓扑序列即可。否则输出 −1。
数据范围 1≤n,m≤105 输入样例 3 3 1 2 2 3 1 3 输出样例 1 2 3
const int N 100010;int n, m; // 题目需要
int h[N], e[N], ne[N], idx; // 构建双重链表
int d[N]; // 节点入度
int q[N]; // 存放结果void add(int a, int b) // 让a指向b
{e[idx] b, ne[idx] h[a], h[a] idx ;
}bool topsort()
{int hh 0, tt -1;for (int i 1; i n; i ) // 寻找入度为0的节点装入queueif (!d[i])q[ tt] i;while (hh tt) // queue不为空{int t q[hh ]; // 取得队列头其入度为0for (int i h[t]; i ! -1; i ne[i]) // 遍历该点所有子节点将子节点入度-1{int j e[i]; // i是idx的地址j是节点if (-- d[j] 0) // 入度-1q[ tt] j; //如果入度为0加入queue}}return tt n - 1;
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof h);for (int i 0; i m; i ){int a, b;scanf(%d%d, a, b);add(a, b);d[b] ; // 入度1}if (!topsort()) puts(-1);else{for (int i 0; i n; i ) printf(%d , q[i]);puts();}return 0;
}例题剑指offerII 114.外星文字典
现有一种使用英语字母的外星文语言这门语言的字母顺序与英语顺序不同。
给定一个字符串列表 words 作为这门语言的词典words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序并 按字母递增顺序 排列。若不存在合法字母顺序返回 “” 。若存在多种可能的合法字母顺序返回其中 任意一种 顺序即可。
字符串 s 字典顺序小于 字符串 t 有两种情况
在第一个不同字母处如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前那么 s 的字典顺序小于 t 。 如果前面 min(s.length, t.length) 字母都相同那么 s.length t.length 时s 的字典顺序也小于 t 。
示例 1
输入words [“wrt”,“wrf”,“er”,“ett”,“rftt”] 输出“wertf”
链接https://leetcode.cn/problems/Jf1JuT
