Cars(Codeforces Round #772(Div. 2))

传送门

题目大意

在\(OX\)轴上有\(n\)辆汽车，我们通过方向(\(L或R\))和初始位置\(ord(各不相同，-10^9\leq ord\leq10^9)\)来表示一辆汽车。然后对于任意两辆汽车有两种状态：相关和不相关。不相关表示两辆汽车分别在当前位置朝着当前方向以任意恒定速度前进都不会相遇，相关表示两辆汽车分别在当前位置朝着当前方向以任意恒定速度前进都能相遇。现在告诉你\(m\)对汽车之间的关系，问能否构造出一种每个汽车的方向和初始位置使得能够满足这\(m\)对汽车之间的关系。\((2\leq n\leq2*10^5,1\leq m\leq\min(2*10^5,{n(n-1)\over2}))\)

思路

首先我们能够发现两辆汽车有关系(无关或有关)当且仅当这两辆汽车的方向相反，于是我们就可以建一张二分图，对于每两辆有关系的汽车，我们都建一条边，然后跑几遍\(dfs\)染个色，如果建出来的不是二分图就可以直接\(“NO”\)了。确定完方向之后，我们再来考虑一下坐标，我们可以发现对于两辆有关系的汽车\(u\)和\(v\)，不妨设汽车\(u\)方向向右，那么当两辆车不相关时，汽车\(v\)在汽车\(u\)的左边，不然就在右边，于是我们就可以在汽车\(u\)和\(v\)之间建一条有向边，然后跑一遍拓扑排序，如果有环，就也可以直接\(“NO”\)了。最后就可以把每辆车的方向和位置输出了，然后这道题就写完了。

代码

#include
using namespace std;
struct edge
{
    int type,u,v;
};
vectoradj[200005];
int col[200005],topo[200005];
void dfs(int v)
{
    for(int u:adj[v])if(col[u]==-1)
    {
        col[u]=col[v]^1;
        dfs(u);
    }
}
bool BipartiteColoring(int n)
{
    for(int i=1;i<=n;i++)col[i]=-1;
    for(int i=1;i<=n;i++)if(col[i]==-1)
    {
        col[i]=0;
        dfs(i);
    }
    for(int i=1;i<=n;i++)for(int j:adj[i])if(col[i]==col[j])return 0;
    return 1;
}
bool TopologicalSort(int n)
{
    vectorin(n+1,0);
    for(int i=1;i<=n;i++)for(int j:adj[i])in[j]++;
    queueq;
    for(int i=1;i<=n;i++)if(in[i]==0)q.push(i);
    int ord=0;
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        topo[v]=ord++;
        for(int u:adj[v])
        {
            in[u]--;
            if(in[u]==0)q.push(u);
        }
    }
    return ord==n;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    vectora(m);
    for(int i=0;i orient left, col = 1 -> orient right
    for(int i=1;i<=n;i++)adj[i].clear();
    for(edge e:a)
    {
        if(col[e.u]==1)swap(e.u,e.v);
        if(e.type==1)adj[e.u].push_back(e.v);
        else adj[e.v].push_back(e.u);
    }
    if(!TopologicalSort(n)){printf("NO\n");return 0;}
    printf("YES\n");
    for(int i=1;i<=n;i++)
    {
        col[i]==1?printf("R %d\n",topo[i]):printf("L %d\n",topo[i]);
    }
    return 0;
}