[拓扑排序] cf 1385E. Directing Edges

题目

题目链接：https://codeforces.ml/contest/1385/problem/E
题目大意：一个图有有向边也有无向边，求如果给无向边加上方向是否有环。如果没有输出加上方向后的所有边，如果有输出NO

思路

可以先对所有有向边拓扑排序一次，求出所有点拓扑的顺序。如果最后还剩有入度不为0的点 则有环。
然后对所有无向边的点 比较他们的拓扑序 令其方向为：
拓扑顺序小 ->拓扑顺序大
因为这样拓扑顺序小的点入度不会被影响 而且在这个点被读过后 拓扑顺序大的点入度也不会被影响

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
#include<fstream>
#include<complex>
#include<algorithm>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
int in[200010],a[200010],s[200010];
vector<int> v[200010];
vector<pair<int,int>> v1,v2;		
int n,m,cnt=1;
void topo(){
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(in[i]==0) q.push(i);
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		cnt++;
		s[u]=cnt;
		for(int i=0;i<v[u].size();i++){
			in[v[u][i]]--;
			if(in[v[u][i]]==0) q.push(v[u][i]);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			in[i]=0;
			s[i]=0;
			v[i].clear();
		}
		v1.clear();
		v2.clear();
		for(int i=1;i<=m;i++){
			int f,b;
			cin>>f>>a[i]>>b;
			if(f){
				in[b]++;
				v[a[i]].push_back(b);
				v2.push_back(make_pair(a[i],b));
			}
			else v1.push_back(make_pair(a[i],b));
		}
		cnt=0;
		topo();
		//cout<<cnt<<endl;
		if(cnt<n) cout<<"NO"<<endl;
		else{
			cout<<"YES"<<endl;
			for(int i=0;i<v2.size();i++){
				cout<<v2[i].first<<" "<<v2[i].second<<endl;
			}
			for(int i=0;i<v1.size();i++){
				if(s[v1[i].first]>s[v1[i].second]) swap(v1[i].first,v1[i].second);
				cout<<v1[i].first<<" "<<v1[i].second<<endl;
			}
		}
	}
    return 0;
}

本文地址：https://blog.csdn.net/kosf_/article/details/107437527