Cars  (Codeforces 1635E)
Tags: Greedy, 2-sat

There are $$$n$$$ cars on a coordinate axis $$$OX$$$. Each car is located at an integer point initially and no two cars are located at the same point. Also, each car is oriented either left or right, and they can move at any constant positive speed in that direction at any moment.More formally, we can describe the $$$i$$$-th car with a letter and an integer: its orientation $$$ori_i$$$ and its location $$$x_i$$$. If $$$ori_i = L$$$, then $$$x_i$$$ is decreasing at a constant rate with respect to time. Similarly, if $$$ori_i = R$$$, then $$$x_i$$$ is increasing at a constant rate with respect to time. We call two cars irrelevant if they never end up in the same point regardless of their speed. In other words, they won't share the same coordinate at any moment.We call two cars destined if they always end up in the same point regardless of their speed. In other words, they must share the same coordinate at some moment.Unfortunately, we lost all information about our cars, but we do remember $$$m$$$ relationships. There are two types of relationships:$$$1$$$ $$$i$$$ $$$j$$$ —$$$i$$$-th car and $$$j$$$-th car are irrelevant.$$$2$$$ $$$i$$$ $$$j$$$ —$$$i$$$-th car and $$$j$$$-th car are destined.Restore the orientations and the locations of the cars satisfying the relationships, or report that it is impossible. If there are multiple solutions, you can output any.Note that if two cars share the same coordinate, they will intersect, but at the same moment they will continue their movement in their directions.

Input: The first line contains two integers, $$$n$$$ and $$$m$$$ $$$(2 \leq n \leq 2 \cdot 10^5; 1 \leq m \leq min(2 \cdot 10^5, \frac{n(n-1)}{2})$$$ — the number of cars and the number of restrictions respectively.Each of the next $$$m$$$ lines contains three integers, $$$type$$$, $$$i$$$, and $$$j$$$ $$$(1 \leq type \leq 2; 1 \leq i,j \leq n; i≠j)$$$.If $$$type$$$ = $$$1$$$, $$$i$$$-th car and $$$j$$$-th car are irrelevant. Otherwise, $$$i$$$-th car and $$$j$$$-th car are destined.It is guaranteed that for each pair of cars, there are at most $$$1$$$ relationship between.

Output: In the first line, print either "YES" or "NO" (in any case), whether it is possible to restore the orientations and the locations of the cars satisfying the relationships.If the answer is "YES", print $$$n$$$ lines each containing a symbol and an integer: $$$ori_i$$$ and $$$x_i$$$ $$$(ori_i \in \{L, R\}; -10^9 \leq x_i \leq 10^9)$$$ — representing the information of the $$$i$$$-th car.If the orientation is left, then $$$ori_i$$$ = $$$L$$$. Otherwise $$$ori_i$$$ = $$$R$$$.$$$x_i$$$ is the where the $$$i$$$-th car is located. Note that all $$$x_i$$$ should be distinct. We can prove that if there exists a solution, then there must be a solution satisfying the constraints on $$$x_i$$$.


Sample Inputs:
4 4
1 1 2
1 2 3
2 3 4
2 4 1

3 3
1 1 2
1 2 3
1 1 3

Sample Outputs:
YES
R 0
L -3
R 5
L 6

NO

Solution (Python):
import sys

def input():
    return sys.stdin.readline()[:-1]

def readline():
    return map(int, input().split())

def main():
    (n, m) = readline()
    edges = [list() for __ in range(n)]
    for __ in range(m):
        (t, i, j) = readline()
        t -= 1
        i -= 1
        j -= 1
        edges[i].append((j, t))
        edges[j].append((i, t))
    ori = [None] * n
    for i in range(n):
        if ori[i] is not None:
            continue
        ori[i] = 0
        q = [i]
        while q:
            i = q.pop()
            assert ori[i] is not None
            for (j, __) in edges[i]:
                if ori[j] is None:
                    ori[j] = ori[i] ^ 1
                    q.append(j)
                elif ori[j] == ori[i]:
                    print('NO')
                    return
    left = [list() for __ in range(n)]
    for i in range(n):
        for (j, t) in edges[i]:
            if t != ori[i]:
                left[i].append(j)
    ans = dict()
    flag = [0] * n

    def topsort(i):
        if flag[i] == 2:
            return True
        flag[i] = 1
        for j in left[i]:
            if flag[j] == 1 or not topsort(j):
                return False
        ans[i] = len(ans)
        flag[i] = 2
        return True
    for i in range(n):
        if i not in ans:
            if not topsort(i):
                print('NO')
                return
    print('YES')
    for i in range(n):
        print('LR'[ori[i]], ans[i])
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def toposort(graph):
    (res, found) = ([], [0] * len(graph))
    stack = list(range(len(graph)))
    while stack:
        node = stack.pop()
        if node < 0:
            res.append(~node)
        elif not found[node]:
            found[node] = 1
            stack.append(~node)
            stack += graph[node]
    for node in res:
        if any((found[nei] for nei in graph[node])):
            return None
        found[node] = 0
    return res[::-1]

def solve():
    (n, m) = map(int, input().split())
    edges = []
    g = [[] for i in range(n)]
    for i in range(m):
        (t, x, y) = map(int, input().split())
        x -= 1
        y -= 1
        edges.append((x, y, t))
        g[x].append(y)
        g[y].append(x)
    c = [-1] * n
    for i in range(n):
        if c[i] != -1:
            continue
        queue = deque()
        queue.append(i)
        c[i] = 0
        while queue:
            x = queue.popleft()
            for y in g[x]:
                if c[y] == -1:
                    c[y] = 1 - c[x]
                    queue.append(y)
                elif c[y] == c[x]:
                    print('NO')
                    return
    g1 = [[] for i in range(n)]
    for (x, y, t) in edges:
        if t + c[y] == 2:
            g1[x].append(y)
        else:
            g1[y].append(x)
    arr = toposort(g1)
    if not arr:
        print('NO')
        return
    print('YES')
    ans = [0] * n
    for (i, a) in enumerate(arr):
        ans[a] = i
    aa = []
    for i in range(n):
        if c[i]:
            aa.append('R ' + str(ans[i]))
        else:
            aa.append('L ' + str(ans[i]))
    print('\n'.join(aa))
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
solve()

Solution (Python):
import sys
from io import BytesIO, IOBase
import os
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inpa():
    return tuple(map(int, input().split()))

def outa(var):
    print(' '.join(map(str, var)))

def redirect_io():
    import pathlib, sys
    fname = pathlib.Path(__file__).parent / 'input.txt'
    sys.stdin = open(fname, 'r')
''
from collections import deque, defaultdict

def top_sort_bfs(graph, n):
    ans = []
    indegree = {node: 0 for node in range(1, n + 1)}
    for nodes in graph.values():
        for node in nodes:
            indegree[node] += 1
    q = deque((node for node in indegree if indegree[node] == 0))
    while q:
        node = q.popleft()
        ans.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)
    return [] if len(ans) != len(graph) else ans
''

def check_biparite(graph) -> dict:

    def bfs(node) -> bool:
        q = deque([(node, 0)])
        node_colors[node] = 0
        while q:
            (cur_node, cur_color) = q.popleft()
            new_color = cur_color ^ 1
            for nbr in graph[cur_node]:
                if nbr in node_colors:
                    if node_colors[nbr] != new_color:
                        return False
                    else:
                        continue
                node_colors[nbr] = new_color
                q.append((nbr, new_color))
        return True
    node_colors = {}
    for node in graph:
        if node in node_colors:
            continue
        if bfs(node) == False:
            return dict()
    return node_colors

def solve(n, m, arr) -> list:
    graph = defaultdict(list)
    for (_, i, j) in arr:
        graph[i].append(j)
        graph[j].append(i)
    coloring_scheme = check_biparite(graph)
    if not coloring_scheme:
        return []
    graph.clear()
    directed_graph = defaultdict(list)
    for (type, i, j) in arr:
        if type == 1:
            if coloring_scheme[i] == 0:
                directed_graph[i].append(j)
            else:
                directed_graph[j].append(i)
        elif type == 2:
            if coloring_scheme[i] == 0:
                directed_graph[j].append(i)
            else:
                directed_graph[i].append(j)
    top_sort = top_sort_bfs(directed_graph, n)
    if not top_sort:
        return []
    directed_graph.clear()
    ans = [0 for _ in range(n)]
    for (i, node) in enumerate(top_sort):
        if node not in coloring_scheme:
            dir = 'R'
        else:
            dir = 'L' if coloring_scheme[node] == 0 else 'R'
        ans[node - 1] = (dir, i)
    return ans
(n, m) = inpa()
arr = [inpa() for _ in range(m)]
ans = solve(n, m, arr)
if ans:
    print('YES')
    print('\n'.join([f'{dir} {loc}' for (dir, loc) in ans]))
else:
    print('NO')