拓扑排序

简介

在计算机科学领域，有向图的拓扑排序是其顶点的线性排序，使得对于从顶点 $u$ 到顶点 $v$ 的每个有向边 $uv$， $u$ 在排序中都在 $v$ 之前。 例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束; 在这个应用中，拓扑排序只是一个有效的任务顺序。 如果且仅当图形没有定向循环，即如果它是有向无环图（DAG），则拓扑排序是可能的。 任何 DAG 具有至少一个拓扑排序，并且已知这些算法用于在线性时间内构建任何 DAG 的拓扑排序。

用一种容器（比如栈，队列，集合）维护当前所有入度为$0$的点。
每次从容器中取出一个点，删掉他和他的出边，这可能导致一些点入度为$0$，将新的入度为$0$的点加入容器。

根据需要，也有可能需要将所有边反向，以倒序生成拓扑排序。

也可以使用DFS生成拓扑排序。

简介

只有有向无环图可以拓扑排序
排序之后，排名靠前的点指向排名靠后的
时间复杂度 O(n + m)

BFS的写法

排名第一 的点一定入度为0
不断删除入度为0的点，更新其他点的入度

DFS的写法

倒序生成拓扑排序
如果想放x，必须把x指向的节点都先放好

一个不太好做的问题

输入一个有向无环图。
问哪些点在拓扑序中的位置是确定的。

似乎只能$O(nm)$暴力。

拓扑排序和动态规划

拓扑排序和动态规划有密不可分的关系。
所有动态规划的所有状态，一定构成一个有向无环图，并且以拓扑序进行更新。

练习题

abc223_d Restricted Permutation

https://atcoder.jp/contests/abc223/tasks/abc223_d

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
vector<int> a[200020];
int d[200020];
set<int> s;
vector<int> z;
int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		a[x].push_back(y);
		d[y]++;
	}
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{
			s.insert(i);
		}
	}
	while (s.size() > 0)
	{
		int x = *s.begin();
		z.push_back(x);
		s.erase(s.begin());
		for (int i: a[x])
		{
			if (--d[i] == 0)
			{
				s.insert(i);
			}
		}
	}
	if (z.size() == n)
	{
		for (int i: z)
		{
			cout << i << " ";
		}
	}
	else
	{
		cout << -1 << endl;
	}
	return 0;
}

题解

https://atcoder.jp/contests/abc223/tasks/abc223_d
求一个长度为n的排列，输入m个限制
第i个限制是ai必须在bi之前
排列字典序越小越好

枚举m
    读入x和y认为是从x到y的一条边
    a[x].push_back(y) // 记录下所有从x出发的边
    y的入度++

枚举所有点i
    如果点i的入度为0
        把i加入集合

当集合非空
    拿出集合中最小的数字x，作为排列的下一个数字
    删去这个数字x
    枚举所有从x出发的边
        这个边指向的点，入度-=1
        如果减成了0
            这个点入集合

如果排列凑齐了n个数字
    那么输出
否则无解

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
vector<int> a[200020];
int d[200020];
set<int> s;
vector<int> z;
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        a[x].push_back(y);
        d[y]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (d[i] == 0)
        {
            s.insert(i);
        }
    }
    while (s.size() > 0)
    {
        int x = *s.begin();
        z.push_back(x);
        s.erase(s.begin());
        for (int i: a[x])
        {
            if (--d[i] == 0)
            {
                s.insert(i);
            }
        }
    }
    if (z.size() == n)
    {
        for (int i: z)
        {
            cout << i << " ";
        }
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}

abc245_f Endless Walk

https://atcoder.jp/contests/abc245/tasks/abc245_f
输入一个有向图，N个点M条边
问有多少个点，作为起点，可以找到无限长的路径？

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z;
vector<int> a[200020];
int d[200020];
queue<int> q;
int main()
{
	cin >> n >> m;
	z = n;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		a[y].push_back(x);
		d[x]++;
	}
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{
			q.push(i);
		}
	}
	while (q.size())
	{
		int u = q.front();
		q.pop();
		z--;
		for (int i : a[u])
		{
			if (!--d[i])
			{
				q.push(i);
			}
		}
	}
	cout << z << endl;
	return 0;
}

题解

abc216_d Pair of Balls

https://atcoder.jp/contests/abc216/tasks/abc216_d

参考代码

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n, m, l;
vector<int> a[200020];
int v[200020];
queue<int> q;
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d", &l);
		a[i].resize(l);
		for (int j = l - 1; j >= 0; j--)
		{
			scanf("%d", &a[i][j]);
		}
		if (v[a[i].back()] > 0)
		{
			q.push(v[a[i].back()]);
			q.push(i);
			n--;
		}
		else
		{
			v[a[i].back()] = i;
		}
	}
	while (q.size())
	{
		int i = q.front();
		q.pop();
		a[i].pop_back();
		if (a[i].size())
		{
			if (v[a[i].back()] > 0)
			{
				q.push(v[a[i].back()]);
				q.push(i);
				n--;
			}
			else
			{
				v[a[i].back()] = i;
			}
		}
	}
	puts(n ? "No" : "Yes");
	return 0;
}

题解

https://atcoder.jp/contests/abc216/tasks/abc216_d
一共有n种球，每种球2个。这2n个球构成m个栈，如果某种球的两个球都在栈顶，可以同时删掉这两个球，问能不能把所有球删完。

icpc2012autumn_a Dictionary

https://atcoder.jp/contests/jag2012autumn/tasks/icpc2012autumn_a

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
string s[500];
vector<int> a[26];
int d[26];
queue<int> q;
void _()
{
	for (int i = 0; i < 26; i++)
	{
		a[i].clear();
		d[i] = 0;
	}
	for (int i = 1; i < n; i++)
	{
		unsigned j = 0;
		while (j < s[i-1].size() && j < s[i].size() && s[i-1][j] == s[i][j])
		{
			j++;
		}
		if (j == s[i-1].size())
		{
			
		}
		else if (j == s[i].size())
		{
			cout << "no" << endl;
			return;
		}
		else
		{
			a[s[i-1][j] - 'a'].push_back(s[i][j] - 'a');
			d[s[i][j] - 'a']++;
		}
	}
	string s;
	for (int i = 0; i < 26; i++)
	{
		if (d[i] == 0)
		{
			q.push(i);
		}
	}
	while (q.size() > 0)
	{
		int x = q.front();
		s += 'a' + x;
		q.pop();
		for (int i: a[x])
		{
			if (--d[i] == 0)
			{
				q.push(i);
			}
		}
	}
	if (s.size() < 26)
	{
		cout << "no" << endl;
	}
	else
	{
		cout << "yes" << endl;	
	}
	return;
}
int main()
{
	while (cin >> n, n)
	{
		for (int i = 0; i < n; i++)
		{
			cin >> s[i];
		}
		_();
	}
	return 0;
}

题解

https://atcoder.jp/contests/jag2012autumn/tasks/icpc2012autumn_a
输入n个字符串，你来决定字母之间的顺序，让这n个字符串有序。

CF510C Fox And Names

https://codeforces.com/problemset/problem/510/C
https://www.luogu.com.cn/problem/CF510C

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
string s[100];
vector<int> a[26];
int d[26];
queue<int> q;
void _()
{
	for (int i = 1; i < n; i++)
	{
		unsigned j = 0;
		while (j < s[i-1].size() && j < s[i].size() && s[i-1][j] == s[i][j])
		{
			j++;
		}
		if (j == s[i-1].size())
		{
			
		}
		else if (j == s[i].size())
		{
			cout << "Impossible" << endl;
			return;
		}
		else
		{
			a[s[i-1][j] - 'a'].push_back(s[i][j] - 'a');
			d[s[i][j] - 'a']++;
		}
	}
	string s;
	for (int i = 0; i < 26; i++)
	{
		if (d[i] == 0)
		{
			q.push(i);
		}
	}
	while (q.size() > 0)
	{
		int x = q.front();
		s += 'a' + x;
		q.pop();
		for (int i: a[x])
		{
			if (--d[i] == 0)
			{
				q.push(i);
			}
		}
	}
	if (s.size() < 26)
	{
		cout << "Impossible" << endl;
	}
	else
	{
		cout << s << endl;	
	}
	return;
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
	}
	_();
	return 0;
}

题解

相邻2个单词可以得到一条边

abcdy
abcdx

a
ab
这样的无法得到任意边
ab
a
这样的直接无解

CF825E Minimal Labels

https://codeforces.com/problemset/problem/825/E
https://www.luogu.com.cn/problem/CF825E

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
vector<int> a[200020];
int d[200020];
int p[200020];
priority_queue<int> q;
int main()
{
	cin >> n >> m;
	int c = n;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		a[y].push_back(x);
		d[x]++;
	}
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{
			q.push(i);
		}
	}
	while (q.size() > 0)
	{
		int x = q.top();
		p[x] = c--;
		q.pop();
		for (int i: a[x])
		{
			if (--d[i] == 0)
			{
				q.push(i);
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		cout << p[i] << ' ';
	}
	return 0;
}

题解

堆优化，拓扑排序

原题要求
点1在拓扑排序中的位置尽量小
点2在拓扑排序中的位置尽量小
点3在拓扑排序中的位置尽量小
...
点n在拓扑排序中的位置尽量小

等价于

让拓扑排序中的第n个点尽量大
让拓扑排序中的第n-1个点尽量大
...
让拓扑排序中的第1个点尽量大

CF883B Berland Army

https://codeforces.com/problemset/problem/883/B
https://www.luogu.com.cn/problem/CF883B

参考代码

题解

CF915D Almost Acyclic Graph

https://codeforces.com/problemset/problem/915/D
https://www.luogu.com.cn/problem/CF915D

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
vector<int> a[520];
int in[520];
int d[520];
int q[520], b, f;
bool ok()
{
	b = f = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!d[i])
		{
			q[f++] = i;
		}
	}
	while (b < f)
	{
		int u = q[b++];
		for (int i: a[u])
		{
			if (!--d[i])
			{
				q[f++] = i;
			}
		}
	}
	return f == n;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		in[y]++;
	}
	for (int i = 1; i <= n; i++)
	{
		memcpy(d, in, sizeof d);
		d[i]--;
		if (ok())
		{
			printf("YES\n");
			return 0;
		}
	}
	printf("NO\n");
	return 0;
}

题解

直接暴力做O(m^2)
转化为枚举点，拓扑排序
时间复杂度O(n(n + m))

CF1100E Andrew and Taxi

https://codeforces.com/problemset/problem/1100/E
https://www.luogu.com.cn/problem/CF1100E

参考代码

题解

二分，改变等价于删除

CF1217D Coloring Edges

https://codeforces.com/problemset/problem/1217/D
https://www.luogu.com.cn/problem/CF1217D

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, c;
int x[5020];
int y[5020];
vector<int> a[5020];
int d[5020];
queue<int> q;
int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> x[i] >> y[i];
		a[x[i]].push_back(y[i]);
		d[y[i]]++;
	}
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{
			q.push(i);
		}
	}
	while (q.size() > 0)
	{
		int x = q.front();
		c++;
		q.pop();
		for (int i: a[x])
		{
			if (--d[i] == 0)
			{
				q.push(i);
			}
		}
	}
	if (c == n)
	{
		cout << 1 << endl;
		for (int i = 0; i < m; i++)
		{
			cout << 1 << ' ';
		}
	}
	else
	{
		cout << 2 << endl;
		for (int i = 0; i < m; i++)
		{
			if (x[i] < y[i])
			{
				cout << 1 << ' ';
			}
			else
			{
				cout << 2 << ' ';
			}
		}
	}
	return 0;
}

题解

有环：2
无环：1

P1038 [NOIP2003 提高组] 神经网络

https://www.luogu.com.cn/problem/P1038

题目背景

人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。

题目描述

在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：

神经元〔编号为 $i$）

图中，$X_1 \sim X_3$ 是信息输入渠道，$Y_1 \sim Y_2$ 是信息输出渠道，$C_1$ 表示神经元目前的状态，$U_i$ 是阈值，可视为神经元的一个内在参数。

神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经元分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。

兰兰规定，$C_i$ 服从公式：（其中 $n$ 是网络中所有神经元的数目）

$C_i=\sum\limits_{(j,i) \in E} W_{ji}C_{j}-U_{i}$

公式中的 $W_{ji}$（可能为负值）表示连接 $j$ 号神经元和 $i$ 号神经元的边的权值。当 $C_i$ 大于 $0$ 时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为 $C_i$。

如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（$C_i$），要求你的程序运算出最后网络输出层的状态。

输入格式

输入文件第一行是两个整数 $n$（$1 \le n \le 100$）和 $p$。接下来 $n$ 行，每行 $2$ 个整数，第 $i+1$ 行是神经元 $i$ 最初状态和其阈值（$U_i$），非输入层的神经元开始时状态必然为 $0$。再下面 $P$ 行，每行由 $2$ 个整数 $i,j$ 及 $1$ 个整数 $W_{ij}$，表示连接神经元 $i,j$ 的边权值为 $W_{ij}$。

输出格式

输出文件包含若干行，每行有 $2$ 个整数，分别对应一个神经元的编号，及其最后的状态，$2$ 个整数间以空格分隔。仅输出最后状态大于 $0$ 的输出层神经元状态，并且按照编号由小到大顺序输出。

若输出层的神经元最后状态均为 $0$，则输出 NULL。

样例 #1

样例输入 #1

5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1

样例输出 #1

3 1
4 1
5 1

提示

【题目来源】

NOIP 2003 提高组第一题

参考代码

题解

拓扑排序，动态规划

P1347 排序

https://www.luogu.com.cn/problem/P1347

题目描述

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 $A,B,C,D$ 表示$A<B,B<C,C<D$。在这道题中，我们将给你一系列形如 $A<B$ 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。

输入格式

第一行有两个正整数 $n,m$，$n$ 表示需要排序的元素数量，$2\leq n\leq 26$，第 $1$ 到 $n$ 个元素将用大写的 $A,B,C,D\dots$ 表示。$m$ 表示将给出的形如 $A<B$ 的关系的数量。

接下来有 $m$ 行，每行有 $3$ 个字符，分别为一个大写字母，一个 < 符号，一个大写字母，表示两个元素之间的关系。

输出格式

若根据前 $x$ 个关系即可确定这 $n$ 个元素的顺序 yyy..y（如 ABC），输出

Sorted sequence determined after xxx relations: yyy...y.

若根据前 $x$ 个关系即发现存在矛盾（如 $A<B,B<C,C<A$），输出

Inconsistency found after x relations.

若根据这 $m$ 个关系无法确定这 $n$ 个元素的顺序，输出

Sorted sequence cannot be determined.

（提示：确定 $n$ 个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）

样例 #1

样例输入 #1

4 6
A<B
A<C
B<C
C<D
B<D
A<B

样例输出 #1

Sorted sequence determined after 4 relations: ABCD.

样例 #2

样例输入 #2

3 2
A<B
B<A

样例输出 #2

Inconsistency found after 2 relations.

样例 #3

样例输入 #3

26 1
A<Z

样例输出 #3

Sorted sequence cannot be determined.

提示

$2 \leq n \leq 26,1 \leq m \leq 600$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[30];
int d[30];
int c[30];
char s[30];
int gao()
{
	// 0 Sorted sequence cannot be determined
	// 1 Sorted sequence determined
	// 2 Inconsistency found after
	memcpy(d, c, sizeof d);
	int f = 1;
	for (int i = 0; i < n; i++)
	{
		int u = -1;
		for (int j = 0; j < n; j++)
		{
			if (d[j] == 0)
			{
				if (u == -1)
				{
					u = j;
				}
				else
				{
					f = 0;
				}
			}
		}
		if (u == -1)
		{
			return 2;
		}
		d[u]--;
		s[i] = 'A' + u;
		for (int j: a[u])
		{
			d[j]--;
		}
	}
	return f;
}
void work()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		char x, y;
		scanf(" %c<%c", &x, &y);
		a[x - 'A'].push_back(y - 'A');
		c[y - 'A']++;
		int t = gao();
		if (t == 1)
		{
			printf("Sorted sequence determined after %d relations: %s.\n", i, s);
			return;
		}
		else if (t == 2)
		{
			printf("Inconsistency found after %d relations.\n", i);
			return;
		}
	}
	printf("Sorted sequence cannot be determined.\n");
	return;
}
int main()
{
	work();
	return 0;
}

题解

枚举所有前缀，求拓扑序
判断拓扑序列是否唯一
每次出队之后，队列大小必须是0

P1983 [NOIP2013 普及组] 车站分级

https://www.luogu.com.cn/problem/P1983

题目描述

一条单向的铁路线上，依次有编号为 $1, 2, …, n$的 $n$个火车站。每个火车站都有一个级别，最低为 $1$ 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 $x$，则始发站、终点站之间所有级别大于等于火车站$x$ 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点）

例如，下表是$5$趟车次的运行情况。其中，前$4$ 趟车次均满足要求，而第 $5$ 趟车次由于停靠了 $3$ 号火车站（$2$ 级）却未停靠途经的 $6$ 号火车站（亦为 $2$ 级）而不满足要求。

现有 $m$ 趟车次的运行情况（全部满足要求），试推算这$n$ 个火车站至少分为几个不同的级别。

输入格式

第一行包含 $2$ 个正整数 $n, m$，用一个空格隔开。

第 $i + 1$ 行$(1 ≤ i ≤ m)$中，首先是一个正整数 $s_i(2 ≤ s_i ≤ n)$，表示第$i$ 趟车次有 $s_i$ 个停靠站；接下来有$s_i$个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

输出格式

一个正整数，即 $n$ 个火车站最少划分的级别数。

样例 #1

样例输入 #1

9 2 
4 1 3 5 6 
3 3 5 6 

样例输出 #1

2

样例 #2

样例输入 #2

9 3 
4 1 3 5 6 
3 3 5 6 
3 1 5 9 

样例输出 #2

3

提示

对于$20\%$的数据，$1 ≤ n, m ≤ 10$；

对于 $50\%$的数据，$1 ≤ n, m ≤ 100$；

对于 $100\%$的数据，$1 ≤ n, m ≤ 1000$。

参考代码

题解

经过的>没经过的，拓扑排序

数据范围比较小，可以暴力
一个优化，通过加点，减少建的边的个数

P2017 [USACO09DEC]Dizzy Cows G

https://www.luogu.com.cn/problem/P2017

题目背景

Hzwer 神犇最近又征服了一个国家，然后接下来却也遇见了一个难题。

题目描述

The cows have taken to racing each other around the farm but they get very dizzy when running in circles, and everyone knows that dizzy cows don't produce any milk. Farmer John wants to convert all of the two-way cow paths in the farm to one-way paths in order to eliminate any 'cycles' and prevent the cows from getting dizzy. A 'cycle' enables a cow to traverse one or more cow paths and arrive back at her starting point, thus completing a loop or circle.

The farm comprises N pastures (1 <= N <= 100,000) conveniently numbered 1..N. M1 (1 <= M1 <= 100,000) one-way cow paths and M2 two-way cow paths (1 <= M2 <= 100,000) connect the pastures. No path directly connects a pasture to itself, although multiple paths might connect two different pastures. A cow may or may not be able to travel between any two given pastures by following a sequence of cow paths.

Your job is to assign a direction to the two-way cow paths such that the entire farm (ultimately with only one-way paths) has no cycles. That is, there should be no sequence of one-way cow paths which leads back to its starting position. The existing one-way cow paths do not form a cycle and should be left as they are.

One-way cow paths run from pasture A_i (1 <= A_i <= N) to pasture B_i (1 <= B_i <= N). Two-way cow paths connect pastures X_i (1 <= X_i <= N) and Y_i (1 <= Y_i <= N).

Consider this example:

1-->2 
|  /| 
| / | 
|/  | 
3<--4 

The cow paths between pastures 1 and 3, 2 and 3, and 2 and 4 are two-way paths. One-way paths connect 1 to 2 and also 4 to 3. One valid way to convert the two-way paths into one-way paths in such a way that there are no cycles would be to direct them from 1 to 3, from 2 to 3, and from 3 to 4:

1-->2 
|  /| 
| / | 
vL  v 
3<--4 

奶牛们发现，在农场里面赛跑是很有趣的一件事.可是她们一旦在农场里面不断地转圈，就 会变得头晕目眩.众所周知，眩晕的奶牛是无法产奶的.于是，农夫约翰想要把他农场里面的双 向道路全部改为单向道路，使得他的农场里面一个圈都没有，以避免他的奶牛们被搞得晕头转 向.如果奶牛可以经过若干条道路回到起点，那么这些道路就称为一个圈.

农场有N(1 < N < 100000)片草地，编号为1到N.这些草地由M1条单向 道路和M2条双向道路连接起来.任何一条道路都不会把一片草地和这篇草地本 身连接起来.但是，任意两片草地之间都可能有多条道路连接.不保证任意两片草地之间都有路 径相连.

你的任务是给所有的双向道路设定一个方向，使得整个农场(只剩下单向道路)最后一个圈都 没有.也就是说，不存在一个单向道路序列的终点和起点重合.数据保证一开始就有的单向道路 中，一个圈都没有.而且一开始就有的单向道路不能改变.

单向道路的起点是草地Ai，终点是草地Bi.双向道路连接草 地Xi,Yi

输入格式

从 dizzy.in 中输入数据

第一行 3 个整数 n，p1，p2，分别表示点数，有向边的数量，无向边的数量。

第二行起输入 p1 行，每行 2 个整数，a，b，表示 a 到 b 有一条有向边。

接下来输入 p2 行，每行 2 个整数 a，b，表示 a 和 b 中间有一条无向边。

输出格式

输出到 dizzy.out 中

对于每条无向边，我们要求按输入顺序输出你定向的结果，也就是如果你输出 a‘b，那

表示你将 a 和 b 中间的无向边定向为 a → b。

注意，也许存在很多可行的解。你只要输出其中任意一个就好。

（注：因为没有spj，我们保证按照常规方法做出的答案一定可以AC）

样例 #1

样例输入 #1

4 2 3
1 2
4 3
1 3
4 2
3 2

样例输出 #1

1 3
4 2
2 3

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, p1, p2, x, y;
vector<int> a[100020];
int in[100020];
int pos[100020], cnt;
int main() {
	cin >> n >> p1 >> p2;
	for (int i = 0; i < p1; i++) {
		cin >> x >> y;
		a[x].push_back(y);
		in[y]++;
	}
	queue<int> q; // stack
	for (int i = 1; i <= n; i++) {
		if (in[i] == 0) {
			q.push(i);
		}
	}
	while (q.size() > 0) {
		int u = q.front(); // top
		q.pop();
		pos[u] = cnt++;
		for (int i = 0; i < a[u].size(); i++) {
			in[a[u][i]]--;
			if (in[a[u][i]] == 0) {
				q.push(a[u][i]);
			}
		}
	}
	for (int i = 0; i < p2; i++) {
		cin >> x >> y;
		if (pos[x] < pos[y]) {
			cout << x << ' ' << y << endl;
		} else {
			cout << y << ' ' << x << endl;
		}
	}
	return 0;
}

题解

根据有向边定向，

#include <bits/stdc++.h>
using namespace std;
int n, p1, p2, x, y;
vector<int> a[100020];
int in[100020];
int pos[100020], cnt;
int main() {
    cin >> n >> p1 >> p2;
    for (int i = 0; i < p1; i++) {
        cin >> x >> y;
        a[x].push_back(y);
        in[y]++;
    }
    queue<int> q; // stack
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            q.push(i);
        }
    }
    while (q.size() > 0) {
        int u = q.front(); // top
        q.pop();
        pos[u] = cnt++;
        for (int i : a[u])
        {
            if (!--in[i])
            {
                q.push(i);
            }
        }
        // for (int i = 0; i < a[u].size(); i++) {
        //     in[a[u][i]]--;
        //     if (in[a[u][i]] == 0) {
        //         q.push(a[u][i]);
        //     }
        // }
    }
    for (int i = 0; i < p2; i++) {
        cin >> x >> y;
        if (pos[x] < pos[y]) {
            cout << x << ' ' << y << endl;
        } else {
            cout << y << ' ' << x << endl;
        }
    }
    return 0;
}

P3183 [HAOI2016]食物链

https://www.luogu.com.cn/problem/P3183

题目描述

如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3......am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链

输入格式

第一行两个整数n和m,接下来m行每行两个整数ai bi描述m条能量流动关系。（数据保证输入数据符号生物学特点，且不会有重复的能量流动关系出现）1<=N<=100000 0<=m<=200000题目保证答案不会爆 int

输出格式

一个整数即食物网中的食物链条数

样例 #1

样例输入 #1

10 16
1 2
1 4
1 10
2 3
2 5
4 3
4 5
4 8
6 5
7 6
7 9
8 5
9 8
10 6
10 7
10 9

样例输出 #1

9

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
vector<int> a[100020];
bool v[100020];
int in[100020];
int f[100020];
void dfs(int x) {
	if (a[x].size() == 0) {
		f[x] = 1;
	}
	for (int i = 0; i < a[x].size(); i++) {
		if (!v[a[x][i]]) {
			dfs(a[x][i]);
		}
		f[x] += f[a[x][i]];
	}
	v[x] = true;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		a[x].push_back(y);
		in[y]++;
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (!v[i]) {
			dfs(i);
		}
		if (in[i] == 0 && a[i].size() > 0) {
			ans += f[i];
		}
	}
	cout << ans << endl;
	return 0;
}

题解

拓扑排序动态规划

P3243 [HNOI2015]菜肴制作

https://www.luogu.com.cn/problem/P3243

题目描述

知名美食家小 A 被邀请至 ATM 大酒店，为其品评菜肴。ATM 酒店为小 A 准备了 $n$ 道菜肴，酒店按照为菜肴预估的质量从高到低给予 $1$ 到 $n$ 的顺序编号，预估质量最高的菜肴编号为 $1$。

由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 $m$ 条形如 $i$ 号菜肴必须先于 $j$ 号菜肴制作的限制，我们将这样的限制简写为 $(i,j)$。

现在，酒店希望能求出一个最优的菜肴的制作顺序，使得小 A 能尽量先吃到质量高的菜肴：

也就是说，

1. 在满足所有限制的前提下，$1$ 号菜肴尽量优先制作。

2. 在满足所有限制，$1$ 号菜肴尽量优先制作的前提下，$2$ 号菜肴尽量优先制作。

3. 在满足所有限制，$1$ 号和 $2$ 号菜肴尽量优先的前提下，$3$ 号菜肴尽量优先制作。

4. 在满足所有限制，$1$ 号和 $2$ 号和 $3$ 号菜肴尽量优先的前提下，$4$ 号菜肴尽量优先制作。

5. 以此类推。

例 1：共 $4$ 道菜肴，两条限制 $(3,1)$、$(4,1)$，那么制作顺序是 $3,4,1,2$。

例 2：共 $5$ 道菜肴，两条限制 $(5,2)$、$(4,3)$，那么制作顺序是 $1,5,2,4,3$。

例 1 里，首先考虑 $1$，因为有限制 $(3,1)$ 和 $(4,1)$，所以只有制作完 $3$ 和 $4$ 后才能制作 $1$，而根据 3，$3$ 号又应尽量比 $4$ 号优先，所以当前可确定前三道菜的制作顺序是 $3,4,1$；接下来考虑 $2$，确定最终的制作顺序是 $3,4,1,2$。

例 $2$ 里，首先制作 $1$ 是不违背限制的；接下来考虑 $2$ 时有 $(5,2)$ 的限制，所以接下来先制作 $5$ 再制作 $2$；接下来考虑 $3$ 时有 $(4,3)$ 的限制，所以接下来先制作 $4$ 再制作 $3$，从而最终的顺序是 $1,5,2,4,3$。现在你需要求出这个最优的菜肴制作顺序。无解输出 Impossible!（首字母大写，其余字母小写）

输入格式

第一行是一个正整数 $t$，表示数据组数。接下来是 $t$ 组数据。对于每组数据：第一行两个用空格分开的正整数 $n$ 和 $m$，分别表示菜肴数目和制作顺序限制的条目数。接下来 $m$ 行，每行两个正整数 $x,y$，表示 $x$ 号菜肴必须先于 $y$ 号菜肴制作的限制。

输出格式

输出文件仅包含 $t$ 行，每行 $n$ 个整数，表示最优的菜肴制作顺序，或者 Impossible! 表示无解。

样例 #1

样例输入 #1

3
5 4
5 4
5 3
4 2
3 2
3 3
1 2
2 3
3 1
5 2
5 2
4 3

样例输出 #1

1 5 3 4 2 
Impossible! 
1 5 2 4 3

提示

【样例解释】

第二组数据同时要求菜肴 $1$ 先于菜肴 $2$ 制作，菜肴 $2$ 先于菜肴 $3$ 制作，菜肴 $3$ 先于。

菜肴 $1$ 制作，而这是无论如何也不可能满足的，从而导致无解。

【数据范围】

$100\%$ 的数据满足 $n,m\le 10^5$，$1\le t\le 3$。

$m$ 条限制中可能存在完全相同的限制。

参考代码

题解

优先队列，拓扑排序
希望 第一个做出的菜标号尽量小
希望 1所在的位置尽量靠前

P4376 [USACO18OPEN]Milking Order G

https://www.luogu.com.cn/problem/P4376

题目描述

Farmer John的$N$头奶牛（$1 \leq N \leq 10^5$），仍然编号为$1 \ldots N$，正好闲得发慌。因此，她们发展了一个与Farmer John每天早上为她们挤牛奶的时候的排队顺序相关的复杂的社会阶层。

经过若干周的研究，Farmer John对他的奶牛的社会结构总计进行了$M$次观察（$1 \leq M \leq 50,000$）。每个观察结果都是他的某些奶牛的一个有序序列，表示这些奶牛应该以与她们在序列中出现的顺序相同的顺序进行挤奶。比方说，如果Farmer John的一次观察结果是序列2、5、1，Farmer John应该在给奶牛5挤奶之前的某个时刻给奶牛2挤奶，在给奶牛1挤奶之前的某个时刻给奶牛5挤奶。

Farmer John的观察结果是按优先级排列的，所以他的目标是最大化$X$的值，使得他的挤奶顺序能够符合前$X$个观察结果描述的状态。当多种挤奶顺序都能符合前$X$个状态时，Farmer John相信一个长期以来的传统——编号较小的奶牛的地位高于编号较大的奶牛，所以他会最先给编号最小的奶牛挤奶。更加正式地说，如果有多个挤奶顺序符合这些状态，Farmer John会采用字典序最小的那一个。挤奶顺序$x$的字典序比挤奶顺序$y$要小，如果对于某个$j$，$x_i = y_i$对所有$i < j$成立，并且$x_j < y_j$（也就是说，这两个挤奶顺序到某个位置之前都是完全相同的，在这个位置上$x$比$y$要小）。

请帮助Farmer John求出为奶牛挤奶的最佳顺序。

输入格式

第一行包含$N$和$M$。接下来的$M$行，每行描述了一个观察结果。第$i+1$行描述了观察结果$i$，第一个数是观察结果中的奶牛数量$m_i$，后面是一列$m_i$个整数，给出这次观察中奶牛的顺序。所有$m_i$的和至多为$200,000$。

输出格式

输出$N$个空格分隔的整数，给出一个$1 \ldots N$的排列，为Farmer John给他的奶牛们挤奶应该采用的的顺序。

样例 #1

样例输入 #1

4 3
3 1 2 3
2 4 2
3 3 4 1

样例输出 #1

1 4 2 3

提示

这里，Farmer John有四头奶牛，他的挤奶顺序应该是奶牛1在奶牛2之前、奶牛2在奶牛3之前（第一个观察结果），奶牛4在奶牛2之前（第二个观察结果），奶牛3在奶牛4之前、奶牛4在奶牛1之前（第三个观察结果）。前两个观察结果可以同时被满足，但是Farmer John不能同时满足所有的规则，因为这样的话会要求奶牛1在奶牛3之前，同时奶牛3在奶牛1之前。

这意味着总共有两种可能的挤奶顺序：1 4 2 3和4 1 2 3，第一种是字典序较小的。

供题：Jay Leeds

参考代码

#include <bits/stdc++.h>
using namespace std;
vector<int> a[100020];
vector<int> b[100020];
vector<int> z;
int n, m;
int in[100020];
priority_queue<int, vector<int>, greater<int> > q;
stack<int> s;
int size()
{
	return q.size() + s.size();
}
void push(int x, bool f)
{
	if (f)
	{
		s.push(x);
	}
	else
	{
		q.push(x);
	}
}
int top(bool f)
{
	int x;
	if (f)
	{
		x = s.top();
		s.pop();
	}
	else
	{
		x = q.top();
		q.pop();
	}
	return x;
}
int ok(int x, bool f)
{
	for (int i = 1; i <= n; i++)
	{
		a[i].clear();
		in[i] = 0;
	}
	for (int i = 0; i < x; i++)
	{
		for (int j = 1; j < b[i].size(); j++)
		{
			a[b[i][j - 1]].push_back(b[i][j]);
			in[b[i][j]]++;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (in[i] == 0)
		{
			push(i, f);
		}
	}
	z.clear();
	while (size())
	{
		z.push_back(top(f));
		for (int i: a[z.back()])
		{
			if (!--in[i])
			{
				push(i, f);
			}
		}
	}
	return z.size() == n;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int l, x;
		scanf("%d", &l);
		for (int j = 0; j < l; j++)
		{
			scanf("%d", &x);
			b[i].push_back(x);
		}
	}
	int L = 0;
	int R = m + 1;
	while (L < R - 1)
	{
		int M = (L + R) / 2;
		(ok(M, 1) ? L : R) = M;
	}
	ok(L, 0);
	for (int i = 0; i < n; i++)
	{
		printf("%d%c", z[i], i == n - 1 ? '\n' : ' ');
	}
	return 0;
}

题解

二分，拓扑排序
如果可以满足前X条件，那么一定可以满足前X-1个条件
如果不能满足前X条件，那么一定不能满足前X+1个条件

#include <bits/stdc++.h>
using namespace std;
vector<int> a[100020];
vector<int> b[100020];
vector<int> z;
int n, m;
int in[100020];
priority_queue<int, vector<int>, greater<int> > q;
stack<int> s;
int size()
{
    return q.size() + s.size();
}
void push(int x, bool f)
{
    if (f)
    {
        s.push(x);
    }
    else
    {
        q.push(x);
    }
}
int top(bool f)
{
    int x;
    if (f)
    {
        x = s.top();
        s.pop();
    }
    else
    {
        x = q.top();
        q.pop();
    }
    return x;
}
int ok(int x, bool f)
{
    for (int i = 1; i <= n; i++)
    {
        a[i].clear();
        in[i] = 0;
    }
    for (int i = 0; i < x; i++)
    {
        for (int j = 1; j < b[i].size(); j++)
        {
            a[b[i][j - 1]].push_back(b[i][j]);
            in[b[i][j]]++;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 0)
        {
            push(i, f);
        }
    }
    z.clear();
    while (size())
    {
        z.push_back(top(f));
        for (int i: a[z.back()])
        {
            if (!--in[i])
            {
                push(i, f);
            }
        }
    }
    return z.size() == n;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int l, x;
        scanf("%d", &l);
        for (int j = 0; j < l; j++)
        {
            scanf("%d", &x);
            b[i].push_back(x);
        }
    }
    int L = 0;
    int R = m + 1;
    while (L < R - 1)
    {
        int M = (L + R) / 2;
        (ok(M, 1) ? L : R) = M;
    }
    ok(L, 0);
    for (int i = 0; i < n; i++)
    {
        printf("%d%c", z[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

P6145 [USACO20FEB]Timeline G

https://www.luogu.com.cn/problem/P6145

题目描述

Bessie 在过去的 $M$ 天内参加了 $N$ 次挤奶。但她已经忘了她每次挤奶是在哪个时候了。

对于第 $i$ 次挤奶，Bessie 记得它不早于第 $S_i$ 天进行。另外，她还有 $C$ 条记忆，每条记忆形如一个三元组 $(a,b,x)$，含义是第 $b$ 次挤奶在第 $a$ 次挤奶结束至少 $x$ 天后进行。

现在请你帮 Bessie 算出在满足所有条件的前提下，每次挤奶的最早日期。

保证 Bessie 的记忆没有错误，这意味着一定存在一种合法的方案，使得：

• 第 $i$ 次挤奶不早于第 $S_i$ 天进行，且不晚于第 $M$ 天进行；
• 所有的记忆都得到满足；

输入格式

第一行三个整数 $N,M,C$。保证 $1 \leq N,C \leq 10^5$，$2 \leq M \leq 10^9$。

接下来一行包含 $N$ 个整数 $S_1, S_2 , \ldots, S_n$，保证 $\forall 1 \leq i \leq n$，都满足 $1 \leq S_i \leq M$。

下面 $C$ 行每行三个整数 $a,b,x$，描述一条记忆。保证 $a \neq b$，且 $1 \leq x \leq M$。

输出格式

输出 $N$ 行，每行一个整数，第 $i$ 行的数表示第 $i$ 次挤奶的最早日期。

样例 #1

样例输入 #1

4 10 3
1 2 3 4
1 2 5
2 4 2
3 4 4

样例输出 #1

1
6
3
8

提示

• 测试点 $2 \sim 4$ 满足 $N,C \leq 10^3$。
• 测试点 $5 \sim 10$ 没有特殊限制。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, c, x, y, z;
vector<pair<int, int> > a[100020];
int d[100020];
int in[100020];
queue<int> q;
int main()
{
	scanf("%d%d%d", &n, &m, &c);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &d[i]);
	}
	for (int i = 0; i < c; i++)
	{
		scanf("%d%d%d", &x, &y, &z);
		a[x].push_back(make_pair(y, z));
		in[y]++;
	}
	for (int i = 1; i <= n; i++)
	{
		if (in[i] == 0)
		{
			q.push(i);
		}
	}
	while (q.size() > 0)
	{
		int u = q.front();
		q.pop();
		for (pair<int, int> i: a[u])
		{
			if (d[i.first] < d[u] + i.second)
			{
				d[i.first] = d[u] + i.second;
			}
			if (!--in[i.first])
			{
				q.push(i.first);
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		printf("%d\n", d[i]);
	}
	return 0;
}

题解

拓扑排序，最长路

d[i] >= s[i]

d[b] >= d[a] + x
d[y] >= d[x] + z
d[i.first] < d[x] + i.second
<  =

对于每个i，都min(d[i])

#include <bits/stdc++.h>
using namespace std;
int n, m, c, x, y, z;
vector<pair<int, int> > a[100020];
int d[100020];
int in[100020];
queue<int> q;
int main()
{
    scanf("%d%d%d", &n, &m, &c);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &d[i]);
    }
    for (int i = 0; i < c; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        a[x].push_back(make_pair(y, z));
        in[y]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 0)
        {
            q.push(i);
        }
    }
    while (q.size() > 0)
    {
        int u = q.front();
        q.pop();
        for (pair<int, int> i: a[u])
        {
            if (d[i.first] < d[u] + i.second)
            {
                d[i.first] = d[u] + i.second;
            }
            if (!--in[i.first])
            {
                q.push(i.first);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d\n", d[i]);
    }
    return 0;
}

P5603 小C与桌游

https://www.luogu.com.cn/problem/P5603

题目背景

小C是一个热爱桌游的高中生，现在他被一个桌游难住了，快来帮帮他！

题目描述

这个桌游的地图可以被抽象成一个 $n$ 个点，$m$ 条边的有向无环图（不保证连通），小C在这个地图上行走，小C能走到某个点当且仅当能够到达这个点的所有点都已经被小C走到。小C会走到每个点恰好 $1$ 次，并且他能走到哪些点与他当前所在的点没有关系（即可以走到与当前所在的点没有连边的点，只要满足之前的条件）。

小C每走到一个标号比之前走到的点都大的点，他就会有 $\frac{1}{2}$ 的概率从对手那里拿到 $1$ 块筹码，有 $\frac{1}{2}$ 的概率给对手 $1$ 块筹码，双方初始各有 $1919810$ 个筹码。

小C的运气时好时坏，所以他希望你帮他计算出：

• 在最优情况下，即他每次都能从对手那里拿到筹码时，他采取最优的行走方式能得到的筹码数。
• 在最劣情况下，即对手每次都能从他那里拿到筹码时，他采取最优的行走方式会失去的筹码数。

输入格式

第一行两个正整数 $n, m$。

接下来 $m$ 行，每行两个正整数 $u, v$，表示地图上有一条有向边 $(u, v)$，不保证无重边。

输出格式

输出两行，每行一个正整数，第一行表示最优情况下小C能拿到的筹码数，第二行表示最劣情况下小C会失去的筹码数。

样例 #1

样例输入 #1

3 2
1 2
1 3

样例输出 #1

3
2

提示

样例解释

最优情况下的行走方式是 $1-2-3$，最劣情况下的行走方式是 $1-3-2$。

计分方式

对于每一个测试点：

• 如果你输出格式错误或者两行都不正确，将会得到 $0$ 分。
• 如果你的输出第一行正确，第二行错误或第二行正确，第一行错误，将会得到这个测试点 $40 \%$ 的分数。
• 否则，你将会得到这个测试点 $100 \%$ 的分数。

数据范围

对于 $20\%$ 的数据，$1 \le n, m \le 10$。

对于 $40\%$ 的数据，$1 \le n, m \le 2000$。

对于 $100\%$ 的数据，$1 \le n, m \le 5 \times 10^5$，$1 \le u, v \le n$。

参考代码

题解

https://www.luogu.com.cn/problem/P5603

树上删叶子

CF1593E Gardener and Tree

https://codeforces.com/problemset/problem/1593/E
https://www.luogu.com.cn/problem/CF1593E

参考代码

题解