题目描述
/给定一个由 nn 个点, mm 条边的有向图
但是这 mm 条边只有部分是 给定方向 的,其余的还 没有确定方向
现在要求我们给所有 未确定方向 的边 确认方向,使得最终图是一个 有向无环图/
看到 DAG(Directed Acyclic Graph),第一时间就想到了 拓扑排序
我们可以根据 已确定方向的边,先 建图
如果 已确定方向的边 构成的图不是一个 DAG,那么无论我们如何给剩下的边确定方向都不可能变成 DAG
所以 拓扑排序 结束后,就可以检查一遍该图是否能成为一个 DAG ,不能则输出 No
如果可以的话,那么就是对剩下 未确定方向 的边,添加 方向
这里很简单了,我们可以直接按照 拓扑序 ,从前往后 添加边,该 加边方案 保证了一定不会形成 环
接着输出答案即可
时间复杂度O(n+m)
参考文献
链式前向星:
https://blog.csdn.net/weixin_45080867/article/details/103098722
https://blog.csdn.net/qq_35356840/article/details/106491902
DAG:
链接:https ://www.acwing.com/solution/content/53750/
//话不多说直接上代码,难点都有注释的哦.
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 200010;
int head[N],nx[N], endd[N];
int du[N],q[N],pos[N];;
int cnt;
int m, n;
struct Edg
{
int a, b;
}edg[N];
void add(int u, int v)// 链式前向星 添加一条边u->v
{
nx[cnt] = head[u];
endd[cnt] = v;
head[u] = cnt++;
}
bool topsort()//拓扑排序
{
int t = -1, ct = 0;
for (int i = 1; i <= n; i++)
if (!du[i])// du[i] 存储点i的入度
q[++t] = i;//所有入度为零的先入队
while (ct <= t)
{
int tm = q[ct++];
//遍历每一个起始入度为1的点所连的边的终点是否入度为1
for (int i = head[tm]; i != -1; i = nx[i])
{
int j = endd[i];//边的终点
if (--du[j] == 0)//终点的入度为1,这里一定要写 --du[j]因为这里要减掉本身的前驱点
q[++t] = j;
}
}
if (t == n - 1)
return true;
else
return false;
}
void solve()
{
int k = 0;
scanf("%d%d", &n, &m);//先输入再初始化
memset(head, -1, (n + 1) * 4);//每个数据四个字节 *4
memset(du, 0, (n + 1) * 4);
cnt = 0;
for (int i = 0; i < m; i++)
{
int fl, a, b;
scanf("%d%d%d", &fl, &a, &b);
if (fl)
add(a, b), ++du[b];//加有向边,则边终点入度+1
else
edg[k++] = { a,b };
}
if (topsort())
{
cout << "YES" << endl;
for (int i = 1; i <= n; i++)//输出有向边
{
for (int j = head[i]; j != -1; j = nx[j])
printf("%d %d\n", i, endd[j]);//i起点,endd[j]终点
}
//输出无向边
for (int i = 0; i < n; i++)
pos[q[i]] = i;
for (int i = 0; i < k; i++)
{
int a = edg[i].a, b = edg[i].b;
if (pos[a] > pos[b])//规定由小到大
printf("%d %d\n", b, a);
else
printf("%d %d\n", a, b);
}
}
else
cout << "NO" << endl;
}
int main()
{
int T;
scanf("%d", &T);
while (T--) solve();
return 0;
}