【Codeforces】1635E Cars 题解

题目大意

有$n$辆车在$x$轴整数上，它们要么向左要么向右行驶。
题目会给出$m$条关系:

• $1,x,y$: 表示$x,y$这两辆车无论速度如何，不可能相遇
• $2,x,y$: 表示$x,y$这两辆车在某些特定速度下，有可能相遇

题目链接

$2\le n\le 2?10^5,2\le m\le 2?10^5$
若可以满足，给出每个汽车的坐标和移动方向。

思路

关系$1,2$都意味着两辆车的移动方向相反。

• 关系$1$:两辆车相向而行
• 关系$2$:两辆车相背而行

所以我们先用二分图来判定是否可以把所有车的方向确定下来。

如果在$1,x,y$中$x$向左行驶，那么$y$就向右行驶，且$x$在$y$的左边,那么我们就在新的图中建立一条边$x\to y$。其它情况可以类比这种操作。

如何判断关系能否被满足？只需在新的图中跑一遍$拓扑排序$即可！

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;const int maxN = 2e5 + 7;int n, m, color[maxN], vis[maxN], d[maxN], ind[maxN];
vector<int> e[maxN], G[maxN];
bool succ;struct op {
    int op, x, y;
}a[maxN];void dfs(int x, int col)
{
    if(!succ)return ;color[x] = col; vis[x] = 1;for(int i = 0; i < e[x].size(); ++i) {
    int y = e[x][i];if(vis[y] && color[y] == col) {
    succ = false;return ;}else if(vis[y])continue;dfs(y, col ^ 1);}
}int main()
{
    scanf("%d%d", &n, &m);for(int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &a[i].op, &a[i].x, &a[i].y);e[a[i].x].push_back(a[i].y);e[a[i].y].push_back(a[i].x);}succ = true;for(int i = 1; i <= n; ++i) {
    if(!succ)break;if(!vis[i])dfs(i, 1);}if(!succ) {
    printf("NO\n");return 0;}for(int i =1; i <= m; ++i) {
    if(a[i].op == 1) {
    if(color[a[i].x] == 1)G[a[i].x].push_back(a[i].y), d[a[i].y]++;else G[a[i].y].push_back(a[i].x), d[a[i].x]++;}else {
    if(color[a[i].x] == 1)G[a[i].y].push_back(a[i].x), d[a[i].x]++;elseG[a[i].x].push_back(a[i].y), d[a[i].y]++;}}queue<int> q;int cnt = 0;for(int i = 1; i <= n; ++i)if(d[i] == 0)q.push(i);while(!q.empty()) {
    int x = q.front(); q.pop();ind[x] = ++cnt;for(int i = 0; i < G[x].size(); ++i) {
    int y = G[x][i];d[y]--;if(d[y] == 0)q.push(y);}}if(cnt != n)printf("NO\n");else {
    printf("YES\n");for(int i = 1; i <= n; ++i) printf("%c %d\n", color[i] == 1? 'L' : 'R', ind[i]);}return 0;
}