グラフの補グラフを求める
無向グラフで、頂点数が
v、辺の数が e のものが与えられています。あなたのタスクは、このグラフの補グラフを求めることです。グラフの補グラフとは、元のグラフで辺が存在しなかった頂点同士をすべて辺でつなぎ、逆に、元のグラフで辺が存在した頂点同士には辺がないように構成されたグラフのことです。
.png?table=block&id=18b2c681-664d-8150-8f67-ea214ab76f3d&cache=v2)
入力
入力の最初の行には、2 つの整数
v (1 ≤ v ≤ 500) と e (1 ≤ e ≤ 100 000) が与えられます。続く
e 行には、整数 v1, v2 (1 ≤ v1, v2 ≤ v) の組が与えられます。これは、頂点 v1 と頂点 v2 が互いに接続されていることを示します。出力
補グラフの隣接リストを出力してください。各行は「頂点の番号 + セミコロン (
:)」の後に、その頂点とつながっている頂点を列挙します。同じ行に並べる頂点の番号は空白で区切ってください。頂点とその隣接頂点の順番は任意です。例
Input | Output |
4 4
1 2
4 2
4 1
3 4 | 1: 3
2: 3
3: 1 2
4: |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB