How Many Paths? (Codeforces 1547G)
Tags: DP, trees

You are given a directed graph $$$G$$$ which can contain loops (edges from a vertex to itself). Multi-edges are absent in $$$G$$$ which means that for all ordered pairs $$$(u, v)$$$ exists at most one edge from $$$u$$$ to $$$v$$$. Vertices are numbered from $$$1$$$ to $$$n$$$.A path from $$$u$$$ to $$$v$$$ is a sequence of edges such that:  vertex $$$u$$$ is the start of the first edge in the path;  vertex $$$v$$$ is the end of the last edge in the path;  for all pairs of adjacent edges next edge starts at the vertex that the previous edge ends on. We will assume that the empty sequence of edges is a path from $$$u$$$ to $$$u$$$.For each vertex $$$v$$$ output one of four values:  $$$0$$$, if there are no paths from $$$1$$$ to $$$v$$$;  $$$1$$$, if there is only one path from $$$1$$$ to $$$v$$$;  $$$2$$$, if there is more than one path from $$$1$$$ to $$$v$$$ and the number of paths is finite;  $$$-1$$$, if the number of paths from $$$1$$$ to $$$v$$$ is infinite. Let's look at the example shown in the figure.  Then:  the answer for vertex $$$1$$$ is $$$1$$$: there is only one path from $$$1$$$ to $$$1$$$ (path with length $$$0$$$);  the answer for vertex $$$2$$$ is $$$0$$$: there are no paths from $$$1$$$ to $$$2$$$;  the answer for vertex $$$3$$$ is $$$1$$$: there is only one path from $$$1$$$ to $$$3$$$ (it is the edge $$$(1, 3)$$$);  the answer for vertex $$$4$$$ is $$$2$$$: there are more than one paths from $$$1$$$ to $$$4$$$ and the number of paths are finite (two paths: $$$[(1, 3), (3, 4)]$$$ and $$$[(1, 4)]$$$);  the answer for vertex $$$5$$$ is $$$-1$$$: the number of paths from $$$1$$$ to $$$5$$$ is infinite (the loop can be used in a path many times);  the answer for vertex $$$6$$$ is $$$-1$$$: the number of paths from $$$1$$$ to $$$6$$$ is infinite (the loop can be used in a path many times). 

Input: The first contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. Then $$$t$$$ test cases follow. Before each test case, there is an empty line.The first line of the test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 4 \cdot 10^5, 0 \le m \le 4 \cdot 10^5$$$) — numbers of vertices and edges in graph respectively. The next $$$m$$$ lines contain edges descriptions. Each line contains two integers $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — the start and the end of the $$$i$$$-th edge. The vertices of the graph are numbered from $$$1$$$ to $$$n$$$. The given graph can contain loops (it is possible that $$$a_i = b_i$$$), but cannot contain multi-edges (it is not possible that $$$a_i = a_j$$$ and $$$b_i = b_j$$$ for $$$i \ne j$$$).The sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$. Similarly, the sum of $$$m$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output: Output $$$t$$$ lines. The $$$i$$$-th line should contain an answer for the $$$i$$$-th test case: a sequence of $$$n$$$ integers from $$$-1$$$ to $$$2$$$.


Sample Inputs:
5

6 7
1 4
1 3
3 4
4 5
2 1
5 5
5 6

1 0

3 3
1 2
2 3
3 1

5 0

4 4
1 2
2 3
1 4
4 3

Sample Outputs:
1 0 1 2 -1 -1 
1 
-1 -1 -1 
1 0 0 0 0 
1 1 2 1

Solution (Python):
import threading
import sys
threading.stack_size(32 * 2048 * 2048)
sys.setrecursionlimit(401000)
from collections import deque
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def getans(index, ans, neigh, visited):
    if ans[index] == -1 or ans[index] == 2:
        return
    if visited[index]:
        ans[index] = -1
        return
    if ans[index] == 1:
        ans[index] = 2
        return
    ans[index] += 1
    visited[index] = 1
    for nextindex in neigh[index]:
        getans(nextindex, ans, neigh, visited)
    visited[index] = 0

def main():
    T = int(input())
    t = 1
    while t <= T:
        s = input()
        (n, m) = map(int, input().split())
        neigh = [[] for i in range(n)]
        for _ in range(m):
            (u, v) = map(int, input().split())
            neigh[u - 1].append(v - 1)
        visited = [0] * n
        ans = [0] * n
        getans(0, ans, neigh, visited)
        queueinf = deque()
        queue2 = deque()
        for i in range(n):
            if ans[i] == 2:
                queue2.append(i)
            if ans[i] == -1:
                queueinf.append(i)
        while queueinf:
            index = queueinf.popleft()
            for nextindex in neigh[index]:
                if ans[nextindex] == -1:
                    continue
                ans[nextindex] = -1
                queueinf.append(nextindex)
        while queue2:
            index = queue2.popleft()
            for nextindex in neigh[index]:
                if ans[nextindex] == -1 or ans[nextindex] == 2:
                    continue
                ans[nextindex] = 2
                queue2.append(nextindex)
        print(' '.join(map(str, ans)))
        t += 1
threading.Thread(target=main).start()

Solution (Python):
import threading
import sys
threading.stack_size(32 * 2048 * 2048)
sys.setrecursionlimit(400010)
from collections import deque
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def getans(index, ans, neigh, visited):
    if ans[index] == -1 or ans[index] == 2:
        return
    if visited[index]:
        ans[index] = -1
        return
    if ans[index] == 1:
        ans[index] = 2
        return
    ans[index] += 1
    visited[index] = 1
    for nextindex in neigh[index]:
        getans(nextindex, ans, neigh, visited)
    visited[index] = 0

def main():
    T = int(input())
    t = 1
    while t <= T:
        s = input()
        (n, m) = map(int, input().split())
        neigh = [[] for i in range(n)]
        for _ in range(m):
            (u, v) = map(int, input().split())
            neigh[u - 1].append(v - 1)
        visited = [0] * n
        ans = [0] * n
        getans(0, ans, neigh, visited)
        queueinf = deque()
        queue2 = deque()
        for i in range(n):
            if ans[i] == 2:
                queue2.append(i)
            if ans[i] == -1:
                queueinf.append(i)
        while queueinf:
            index = queueinf.popleft()
            for nextindex in neigh[index]:
                if ans[nextindex] == -1:
                    continue
                ans[nextindex] = -1
                queueinf.append(nextindex)
        while queue2:
            index = queue2.popleft()
            for nextindex in neigh[index]:
                if ans[nextindex] == -1 or ans[nextindex] == 2:
                    continue
                ans[nextindex] = 2
                queue2.append(nextindex)
        print(' '.join(map(str, ans)))
        t += 1
threading.Thread(target=main).start()

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
from collections import deque

def cyc(n, path):
    (visi, poi) = ([2] + [0] * (n - 1), [0] * n)
    inf = []
    multi = []
    st = [0]
    while len(st):
        (x, y) = (st[-1], poi[st[-1]])
        if y == len(path[x]):
            visi[st.pop()] = 1
        else:
            z = path[x][y]
            if visi[z] == 2:
                inf.append(z)
                poi[x] += 1
                continue
            if visi[z] == 1:
                multi.append(z)
                poi[x] += 1
                continue
            st.append(z)
            poi[x] += 1
            visi[z] = 2
    ans = [1] * n
    for i in range(n):
        if not visi[i]:
            ans[i] = 0
    curr = deque(multi)
    vv = [0] * n
    for i in multi:
        vv[i] = 1
    while len(curr):
        x = curr.popleft()
        ans[x] = 2
        for y in path[x]:
            if not vv[y]:
                vv[y] = 1
                curr.append(y)
    curr = deque(inf)
    vv = [0] * n
    for i in inf:
        vv[i] = 1
    while len(curr):
        x = curr.popleft()
        ans[x] = -1
        for y in path[x]:
            if not vv[y]:
                vv[y] = 1
                curr.append(y)
    return ans

def main():
    for _ in range(int(input())):
        input()
        (n, m) = map(int, input().split())
        path = [[] for _ in range(n)]
        for _ in range(m):
            (aa, bb) = map(int, input().split())
            path[aa - 1].append(bb - 1)
        print(*cyc(n, path))
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')
if __name__ == '__main__':
    main()