CodeForces 1385E. Directing Edges(拓扑排序)

题意:你被给予了n个点m条边。不保证这个图是否联通。一些边已经被定向了，并且你无法改变它们的方向。一些边还没有定向，你需要为这些边选择一些方向。你需要给这些没有定向的边定一个方向，使得这个图是有向无环图。

分析:将所有边存在一个数组里，然后对有向图的边进行拓扑排序，得到所有顶点依次出现的顺序，我们用一个数组(pos)记录。然后判断pos[]数组的大小，依次输出方案。拓扑排序可以判断这个图是否有环。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 200005;
int h[N], e[N * 2], ne[N * 2], idx;
int d[N], q[N];
int pos[N];
int n, m;
vector<pair<int, int>> edges;
void add(int a, int 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)
	{
		if (d[i] == 0)
		{
			q[++tt] = i;
		}
	}
	while (hh <= tt)
	{
		int t = q[hh++];
		for (int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i];
			--d[j];
			if (d[j] == 0)
			{
				q[++tt] = j;
			}
		}
	}
	return tt == n - 1;
}

int main()
{	
	int t;
	scanf("%d", &t);

	while (t--)
	{
		memset(h, -1, sizeof h);
		idx = 0;
		scanf("%d%d", &n, &m);

		int ty;
		int u, v;
		for (int i = 1; i <= m; ++i)
		{
			scanf("%d%d%d", &ty, &u, &v);
			if (ty == 1)
			{
				add(u, v);
				++d[v];
			}
			edges.push_back({ u, v });
		}

		bool flag = topsort();

		if (!flag)
		{
			puts("NO");
		}
		else
		{
			puts("YES");

			for (int i = 0; i < n; ++i)
			{
				pos[q[i]] = i + 1;
			}

			//给每条边定向
			for (auto [x, y] : edges)
			{
				if (pos[x] < pos[y])
				{
					printf("%d %d
", x, y);
				}
				else
				{
					printf("%d %d
", y, x);
				}
			}
		}
		for (int i = 0; i <= n; ++i)
		{
			d[i] = 0;
		}
		edges.clear();
	}
	
	return 0;
}