一、题目
1、原题链接
3696. 构造有向无环图
2、题目描述
给定一个由 n 个点和 m 条边构成的图。
不保证给定的图是连通的。
图中的一部分边的方向已经确定，你不能改变它们的方向。
剩下的边还未确定方向，你需要为每一条还未确定方向的边指定方向。
你需要保证在确定所有边的方向后，生成的图是一个有向无环图（即所有边都是有向的且没有有向环的图）。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含两个整数 n,m。
接下来 m 行，每行包含三个整数 t,x,y，用来描述一条边的信息，其中 t 表示边的状态，如果 t=0，则表示边是无向边，如果
t=1，则表示边是有向边。x,y 表示这条边连接的两个端点，如果是有向边则边的方向是从 x 指向 y。
保证图中没有重边（给定了 (x,y)，就不会再次出现 (x,y) 或出现 (y,x) 和自环（不会出现 x=y 的情况）。
输出格式
对于每组数据，如果无法构造出有向无环图，则输出一行 NO。
否则，先输出一行 YES，随后 m 行，每行包含两个整数 x,y，用来描述最终构造成的有向无环图中的每条边的具体方向（x 指向
y），边的先后顺序随意。
注意，已经确定方向的边，不能更改方向。如果答案不唯一，输出任意合理方案均可。
数据范围
对于前三个测试点，1≤n,m≤10。
对于全部测试点，1≤T≤20000，2≤n≤2×105，1≤m≤min(2×105,n(n−1)/2)，0≤t≤1，1≤x,y≤n。
保证在一个测试点中，所有 n 的和不超过 2×105，所有 m 的和不超过 2×105。
输入样例：
4
3 1
0 1 3
5 5
0 2 1
1 1 5
1 5 4
0 5 2
1 3 5
4 5
1 1 2
0 4 3
1 3 1
0 2 3
1 2 4
4 5
1 4 1
1 1 3
0 1 2
1 2 4
1 3 2
输出样例：
YES
3 1
YES
2 1
1 5
5 4
2 5
3 5
YES
1 2
3 4
3 1
3 2
2 4
NO
二、解题报告
1、思路分析
思路来源：y总yyds
y总yyds
（1）如果给定图中存在回路（即无法构成构成拓扑序列）则无论怎样为无向边添加方向，都不可能无环，所以此时无解。
（2）如果给定的图中不存在回路（即存在拓扑序列），则可以将与无向边相连的点，在拓扑序列中前面的点指向后面的点，这样为每条边添加方向，不会存在环。
（3）按上述模拟，先输出所有有向边，然后再按（2）输出所有无向边（同时为无向边添加方向）。
2、时间复杂度
拓扑排序时间复杂度为O(n+m)（n为点数，m为边数）
3、代码详解
/*注：使用cin、cout最后一个测试数据会超时*/
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200010,M=N; //N代表点数，M代表边数
//邻接表存储有向边
int h[N],e[M],ne[M],idx; //h[]存储每个点的第一条边的idx，e[]存储每条边的终点，ne[]存储每个点同起点下一条边的idx，idx为边的编号
int d[N]; //记录每个点的入度
int ans[N]; //记录拓扑序列
int pos[N]; //记录每个点在拓扑排序中的位置
int n,m,T;
//存储无向边
struct Edge{
int a,b;
}edge[M];
//邻接表中添加一条边
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
//拓扑排序
bool tp(){
queue<int> q;
int ord=0,num=0; //ord记录每个点入队顺序，也就是在拓扑序列中的先后顺序
for(int i=1;i<=n;i++){
if(d[i]==0) q.push(i),pos[i]=++ord;
}
while(!q.empty()){
int t=q.front();
q.pop();
ans[num++]=t;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
d[j]--;
if(d[j]==0) q.push(j),pos[j]=++ord;
}
}
return num==n;
}
int main(){
cin>>T;
while(T--){
memset(h,-1,sizeof h);
memset(d,0,sizeof d);
idx=0;
scanf("%d%d",&n,&m);
int t,x,y;
int cnt=0;
while(m--){
scanf("%d%d%d",&t,&x,&y);
if(t==0) edge[cnt++]={x,y};
else{
add(x,y);
d[y]++;
}
}
if(!tp()) puts("NO");
else{
puts("YES");
//先输出所有有向边
for(int i=1;i<=n;i++){
for(int j=h[i];j!=-1;j=ne[j]){
printf("%d %d\n",i,e[j]);
}
}
//输出无向边的同时给边“确定方向”
for(int i=0;i<cnt;i++){
int x=edge[i].a,y=edge[i].b;
if(pos[x]>pos[y]) swap(x,y); //拓扑序列中前面的点指向后面的点
printf("%d %d\n",x,y);
}
}
}
return 0;
}
三、知识风暴
拓扑排序
拓扑序列满足：如果存在vi到vj的路径，则顶点vi必然在顶点vj之前。
拓扑排序过程：
从有向图中选择一个没有前驱（即入度为0）的点并且输出。
从图中删去该顶点，并且删去从该顶点发出的全部有向边。
重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。
