【Codeforces】1635E Cars 题解

ACM/OI 算法 Codeforeces 图论拓扑排序二分图

ACM-ICPC

Publish Date: 2022-03-01

题目大意

有 $n$ 辆车在 $x$ 轴整数上，它们要么向左要么向右行驶（$2 \le n \le 2 \times 10^5$，$2 \le m \le 2 \times 10^5$）。题目会给出 $m$ 条关系：

1 x y：表示 $x, y$ 这两辆车无论速度如何，不可能相遇（相向而行）
2 x y：表示 $x, y$ 这两辆车在某些特定速度下，有可能相遇（相背而行）

若可以满足，给出每个汽车的坐标和移动方向。

题目链接

思路

关系 1、2 都意味着两辆车的移动方向相反：

关系 1：两辆车相向而行
关系 2：两辆车相背而行

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

之后，如果在关系 1 x y 中 $x$ 向左行驶，那么 $y$ 就向右行驶，且 $x$ 在 $y$ 的左边，那么我们就在新的图中建立一条边 $x \rightarrow 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]++;
            else
                G[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;
}