Problem:
	
C: 同値命題

	
問題

	

		$N$ 個の命題があり, それぞれ $1, 2, \cdots,N$ という名前がついている. 

		また, 命題に関する情報が $M$ 個与えられる. $i$ 番目の情報は「$a_i$ $b_i$」という形式で与えられ, これは $a_i$ ならば $b_i$ であることを表す.（「ならば」は論理包含であり、推移律が成り立つ）

		各命題 $i$ に対して $i$ と同値な命題を全て昇順に出力せよ.

		ただし命題 $i$ と命題 $i$ は常に同値である.

		命題 $X$ と命題 $Y$ が同値とは,「$X$ ならば $Y$」かつ「$Y$ ならば $X$」のことである.
	

	
制約

	

		
入力値は全て整数である.

		
$ 2 \leq N \leq 300$

		
$ 1 \leq M \leq N(N - 1)$

		
$ a_i \neq b_i $

		
$1 \leq a_i, b_i \leq N $

	

	
入力形式

	
 入力は以下の形式で与えられる. 

	

		$N\ M$

		$a_1\ b_1$

		$a_2\ b_2$

		$\vdots$

		$a_M\ b_M$

	

	
出力

	

		$i$ 行目には命題 $i$ と同値である命題を昇順に空白区切りですべて出力せよ. また, 各行の末尾に改行を出力せよ.
	

	
サンプル

	
サンプル入力 1

	

5 2
1 2
2 1

	
サンプル出力 1

	

1 2
1 2
3
4
5

	
サンプル入力 2

	

3 3
1 2
2 3
3 1

	
サンプル出力 2

	

1 2 3
1 2 3
1 2 3

	
サンプル入力 3

	

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

	
サンプル出力 3

	

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



Sample input:
5 2
1 2
2 1


Sample output:
1 2
1 2
3
4
5

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M = inpl()

G = [[] for _ in range(N)]
rG = [[] for _ in range(N)]

for i in range(M):
    a, b = inpl()
    G[a-1].append(b-1)
    rG[b-1].append(a-1)

def SCC(G, rG):
    N = len(G)
    def dfs(i):
        nonlocal t, rorder, searched
        searched[i] = True
        for j in G[i]:
            if not searched[j]:
                dfs(j)
        rorder[t] = i
        t += 1

    def rdfs(i):
        nonlocal t, group, g
        group[i] = g
        for j in rG[i]:
            if group[j] == -1:
                rdfs(j)

    t = 0
    rorder = [-1]*N
    searched = [0]*N
    group = [-1]*N

    for i in range(N):
        if not searched[i]:
            dfs(i)
    g = 0
    for i in range(N-1, -1, -1):
        if group[rorder[i]] == -1:
            rdfs(rorder[i])
            g += 1
    return group, g

group, g = SCC(G, rG)

ans = [[] for _ in range(g)]
for i in range(N):
    ans[group[i]].append(i+1)

for i in range(N):
    print(*ans[group[i]])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
graph = [[] for _ in range(n)]
for _ in range(m):
    a,b = LI()
    graph[a-1].append(b-1)

def dfs(s,lst,graph,check):
    lst.append(s)
    check[s] = False
    for v in graph[s]:
        if check[v]:
            dfs(v,lst,graph,check)
    return lst
L = []
for i in range(n):
    c = [True]*n
    l = dfs(i,[],graph,c)
    l.sort()
    L.append(l)

ans = [[] for _ in range(n)]
for i in range(n):
    for j in L[i]:
        if i in L[j]:
            ans[i].append(j+1)
for i in range(n):
    print(*ans[i])

Submission status: Accepted

Solution code:
# https://tjkendev.github.io/procon-library/python/graph/scc.html
# 強連結成分分解(SCC): グラフGに対するSCCを行う
# 入力: <N>: 頂点サイズ, <G>: 順方向の有向グラフ, <RG>: 逆方向の有向グラフ
# 出力: (<ラベル数>, <各頂点のラベル番号>)
def scc(N, G, RG):
    order = []
    used = [0]*N
    group = [None]*N
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)
    for i in range(N):
        if not used[i]:
            dfs(i)
    used = [0]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1
    return label, group

N, M = map(int, input().split())
E1 = [[] for _ in range(N+1)]
E2 = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    E1[a].append(b)
    E2[b].append(a)
label, group = scc(N+1, E1, E2)
for g in group[1:]:
    ans = []
    for n, gg in enumerate(group[1:], 1):
        if g == gg:
            ans.append(n)
    print(" ".join(map(str, ans)))