Cars 二分图染色/拓扑排序

题意

坐标轴 $X$ 上有 $n$ 辆汽车。每辆车最初位于一个整数点，并且没有两辆车位于同一点。此外，每辆车都可以向左或向右定向地、可以随时以任何恒定的正速度地沿该方向移动。定义两种关系：

如果两辆汽车无论速度如何都永远不会到达同一点，我们称它们为 无关紧要的。换句话说，它们在任何时候都不会处于相同的坐标。

如果两辆汽车无论速度如何，它们一定会到达同一点，我们就称它们为命中注定的。换句话说，它们一定会在某个时刻处于相同的坐标。

我们知道n量汽车之间的m 个关系。有两种类型的关系：

1 i j— 第 i 辆车和第 j 辆车是 无关紧要的。
2 i j— 第 i 辆车和第 j 辆车是 命中注定的。

要求求出满足关系的汽车的方向和位置，或着回答满足关系的车不可能存在的。如果有多个解决方案，则输出任何一个。

题解

题中的两种关系都是与速度无关的，即要么相向而行，要么背道而驰，通过观察，我们可以发现这两种关系都满足方向相反。

考虑矛盾的情况。建图，$m$对点之间用无向边相连，代表有关系（两种关系其中一种），根据上面知道，有关系的两辆车行驶方向相反，通过染色法来表示就是相邻两点颜色应该不同，因此可以通过染色法排除矛盾的情况。

然后再考虑车辆的位置关系。重新建图，建图规则是$i \to j$，当且仅当$x_i < x_j$，即顶点i在坐标轴上的位置小于j对应的位置。这个过程需要自己判断，先规定$col[i] = 0$为i车向左行驶，每一对关系点$(u, v)$，行驶方向必然不同，我们先将u点确定为向左行驶，即如果$col[u] = 1$, 就交换$u$,$v$的值，然后就可以根据相离或相向的关系建边了。这个建成的图应该是一个$DAG$图（有向无环图），其中的拓扑序就可以代表每个点在数轴上的位置。

int n, m;
int cnt = 0;
int flag = 0;
int in[maxn];
int col[maxn];
vector<int> G[maxn];
int vis[maxn], ans[maxn];
int re[maxn], t1[maxn], t2[maxn];
void dfs(int x, int t) {

col[x] = t;

vis[x] = 1;

for (auto i : G[x]) {

if (vis[i] && col[i] == t) {

flag = 1;

return ;

}

if (flag || vis[i]) continue;

dfs(i, t ^ 1);

}

}
bool topsort() {

queue<int> q;

for (int i = 1; i <= n; i ++) if (in[i] == 0) q.push(i);

while (!q.empty()) {

int x = q.front();

q.pop();

ans[x] = ++ cnt;

for (auto i : G[x]) {

if (-- in[i] == 0) {

q.push(i);

}

}

}

return (cnt == n);

}
void solve() {
cin </span>&gt;&gt; n &gt;&gt;<span style="color: #000000;"> m;
</span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">1</span>; i &lt;= m; i ++<span style="color: #000000;">) {
    </span><span style="color: #0000ff;">int</span><span style="color: #000000;"> t, u, v;
    cin </span>&gt;&gt; t &gt;&gt; u &gt;&gt;<span style="color: #000000;"> v;
    re[i] </span>= t, t1[i] = u, t2[i] =<span style="color: #000000;"> v;
    G[u].push_back(v);
    G[v].push_back(u);
}
</span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">1</span>; i &lt;= n; i ++) <span style="color: #0000ff;">if</span> (!vis[i]) dfs(i, <span style="color: #800080;">1</span><span style="color: #000000;">);
</span><span style="color: #0000ff;">if</span><span style="color: #000000;"> (flag) {
    cout </span>&lt;&lt; <span style="color: #800000;">"</span><span style="color: #800000;">NO\n</span><span style="color: #800000;">"</span><span style="color: #000000;">;
    </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> ;
}
</span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">1</span>; i &lt;= n; i ++<span style="color: #000000;">) G[i].clear();

</span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">1</span>; i &lt;= m; i ++<span style="color: #000000;">) {
    </span><span style="color: #0000ff;">int</span> type = re[i], u = t1[i], v =<span style="color: #000000;"> t2[i];
    </span><span style="color: #0000ff;">if</span> (col[u] == <span style="color: #800080;">1</span>) swap(u, v); <span style="color: #008000;">//</span><span style="color: #008000;"> 规定u指向特定方向L</span>
    <span style="color: #0000ff;">if</span> (type == <span style="color: #800080;">1</span>) G[u].push_back(v), <span style="color: #0000ff;">in</span>[v] ++<span style="color: #000000;">;
    </span><span style="color: #0000ff;">else</span> G[v].push_back(u), <span style="color: #0000ff;">in</span>[u] ++<span style="color: #000000;">;
}
</span><span style="color: #0000ff;">if</span><span style="color: #000000;"> (topsort()) {
    cout </span>&lt;&lt; <span style="color: #800000;">"</span><span style="color: #800000;">YES\n</span><span style="color: #800000;">"</span><span style="color: #000000;">;
    </span><span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">1</span>; i &lt;= n; i ++) cout &lt;&lt; ((col[i] == <span style="color: #800080;">0</span>) ? <span style="color: #800000;">'</span><span style="color: #800000;">L</span><span style="color: #800000;">'</span> : <span style="color: #800000;">'</span><span style="color: #800000;">R</span><span style="color: #800000;">'</span>) &lt;&lt; <span style="color: #800000;">"</span> <span style="color: #800000;">"</span> &lt;&lt; ans[i] &lt;&lt;<span style="color: #000000;"> endl;
} </span><span style="color: #0000ff;">else</span> cout &lt;&lt; <span style="color: #800000;">"</span><span style="color: #800000;">NO\n</span><span style="color: #800000;">"</span><span style="color: #000000;">;

}