题目保证了一开始图为 DAG，因此入度和出度为 \(0\) 的点都是存在的。那么先找一个出度为 \(0\) 的点，再把所有入度为 \(0\) 的点进入队列。每次取出队首，与出度为 \(0\) 的点，进行一次操作。操作后，这个点的出度变为 \(0\)，可以在下次操作使用（这样也保证了每个点的出度不超过 \(1\)）。同时要更新这个点的出边所对应的点。
因此只需要 \(n-1\) 次操作（初始出度为 \(0\) 的点不必），时间复杂度 \(O(n+m)\)。
#include <iostream>
#include <cstdio>
#include <vector>using namespace std;vector<int> G[1000001];
int q[1000001],x,y,t,w,vis[1000001];
int n,m,id[1000001],od[1000001];int main()
{int u,v;cin >> n >> m;for( int i = 1 ; i <= m ; i ++ ){cin >> u >> v;od[u] ++;id[v] ++;G[u].push_back( v );}for( int i = 1 ; i <= n ; i ++ ){if( od[i] == 0 ) y = i;if( id[i] == 0 ) q[++ w] = i;}vis[y] = 1;cout << n - 1 << '\n';for( int i = 1 ; i < n ; i ++ ){t ++;x = q[t];cout << x << ' ' << y << '\n';for( auto v : G[x] ){id[v] --;if( id[v] == 0 && v != y )q[++ w] = v;}y = x;}return 0;
}