グラフの転置を求める

頂点数 v と辺数 e を持つ有向グラフが与えられたとき、その転置を求めなさい。

有向グラフの転置とは、すべての辺の向きを逆にすることで得られるグラフを指します。つまり、元のグラフにあるすべての有向辺を反転させたものです。

profound.academy-graph-transpose.drawio.png

グラフの転置は、逆方向の経路や逆関係を調べる際に役立ちます。本コースの後半では、その具体的な応用についても取り上げる予定です。

入力

入力の最初の行には、整数 v (1 ≤ v ≤ 100 000) と e (1 ≤ e ≤ 100 000) が与えられます。

続く e 行には、v1v2 (1 ≤ v1, v2 ≤ v) が与えられ、これは頂点 v1 と頂点 v2 が辺で結ばれていることを意味します。

出力

プログラムは、補グラフ (complement graph) の隣接リストを出力してください。各行は、頂点のIDを書いた後にセミコロン (:) を置き、続けてその頂点に隣接する頂点を空白区切りで並べます。頂点および接続先の順番は任意です。

入力

出力

4 4
1 2
1 4
2 4
3 4

1:
2: 1
3:
4: 1 2 3

Constraints

Time limit: 3.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue