CF1635E Cars

题意：给定m对汽车之间的关系（无关紧要或命中注定·）。

1. 无关紧要：无论两辆汽车的速度是多少都不会相遇。
2. 命中注定：无论两辆汽车的速度是多少都一定会相遇。
   对每辆车给出一个行驶方向和起点使得m个关系成立。
   思路：
   首先我们考虑无关紧要可以证明，如果两车同向，只要让较后的车速度更快一定会相遇。所以两车一定是异向的。再考虑下图的这种情况，虽然两车是异向的，但还是会相遇。所以向左行驶的车起点一定要在向右行驶的车的左边。

而命中注定正是:
向左行的车起点在向右行的车的右边。
(命中注定并不能同向行驶)

于是我们可以考虑给原来二分图的边定向：若 \(x_u<x_v\) 则连边 \(u\to v\)，反之亦然。

这样下来，发现这些约束关系是天然的偏序关系，有解当且仅当图是张 \(DAG\)，并且需要求方案的话输出拓扑序就可以了。所以总结一下算法流程：二分图染色（判断无解），给边定向，拓扑排序（判断无解）并给点赋坐标。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int vis[200001],pos[200001];
int now;
struct stu{
	int xx;
	int yy;
	int col;
}rela[200001];

vector<int> v[200001],g[200001];
queue<int> q;
int in[200001];

void dfss(int u,int c){
	vis[u]=c;
	for(int i=0;i<v[u].size();i++){
		if(vis[v[u][i]]==c){
			cout<<"NO";
			exit(0);
		}
	}
	for(int i=0;i<v[u].size();i++){
		if(!vis[v[u][i]]) dfss(v[u][i],-c);
	}
}

void dfs(){
	while(!q.empty()){
		int o=q.front();
		q.pop();
		pos[o]=++now;
		for(int i=0;i<v[o].size();i++){
			in[v[o][i]]--;
			if(in[v[o][i]]==0) q.push(v[o][i]);
		}
	}	
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>rela[i].col>>rela[i].xx>>rela[i].yy;
	}
	for(int i=1;i<=m;i++){
		v[rela[i].xx].push_back(rela[i].yy);
		v[rela[i].yy].push_back(rela[i].xx);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]) dfss(i,-1);
	}
	for(int i=1;i<=m;i++){
		if(vis[rela[i].xx]==1) swap(rela[i].xx,rela[i].yy);
		if(rela[i].col==1) g[rela[i].xx].push_back(rela[i].yy),in[rela[i].yy]++;
		else g[rela[i].yy].push_back(rela[i].xx),in[rela[i].xx]++;
	}
	for(int i=1;i<=n;i++) if(in[i]==0) q.push(i);
	dfs();
	if(now<n){
		cout<<"NO";
		return 0;
	}
	else{
		cout<<"YES"<<endl;
		for(int i=1;i<=n;i++){
			if(vis[i]==-1) cout<<"L "<<pos[i]<<endl;
			else cout<<"R "<<pos[i]<<endl;
		}
	}
	return 0;
}