CF - 1385E -- Directing Edges【拓扑排序】

Directing Edges

题意：

给n个点，m条边，每次输入m个关系， 每行有t，x，y。如果t是0则表示x到y是
无向边，t等于1则表示x到y是有向边,问,如果图有环，输出No，否则输出Yes，
并且输出任意有向图。

思路：

 利用拓扑排序检查是否有环。题中告诉没有重复的路径，那么我们在存图时，将所有边都存一遍，有向边特殊存。我们利用拓扑排序时，存一下每个结点出来的先后顺序。在对已有的边进行输出的时候。判断先后输出即可。 

AC代码

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int>	pll;
const int maxn = 2e5 + 5;
vector<int> g[maxn];
vector<pll>	edges;
int ind[maxn];
int pos[maxn];
bool KahnTopological(int n){queue<int>	q;for (int i = 0; i < n; ++i){if (ind[i] == 0){q.push(i);}}int cnt = 0;while (!q.empty()){int u = q.front(); q.pop();pos[u] = cnt++; for (int i = 0; i < g[u].size(); i++){int v = g[u][i];--ind[v];if (ind[v] == 0){q.push(v);}}}if (cnt == n){puts("YES");for (int i = 0; i < edges.size(); ++i){int u = edges[i].first;int v = edges[i].second;if (pos[u] > pos[v])	swap(u,v);printf("%d %d\n",u+1,v+1);}} else{puts("No");}
}
void init(int n){for (int i = 0; i < n; ++i){g[i].clear();ind[i] = 0;pos[i] = 0;}edges.clear();
}
void solve(){int n, m, t, x, y;scanf("%d%d", &n, &m);init(n);for (int i = 0; i < m; ++i){scanf("%d%d%d", &t, &x, &y);--x, --y; edges.push_back(pll(x, y));if(t == 1){g[x].push_back(y);++ind[y];}}KahnTopological(n);
}
int main(){int t;scanf("%d", &t);for (int i = 0; i < t; ++i)	solve();return 0;
}