Day 071-Q2 | 区間グラフ認識（Interval Graph Recognition・MCS応用）

問題

$N$ 頂点 $M$ 辺の無向グラフ $G$ が与えられる。以下を処理せよ。

$G$ が区間グラフ（Interval Graph）か判定せよ。
区間グラフならば、各頂点 $v$ に対する区間 $[l_v, r_v]$ を出力。
区間グラフでない場合は NO を出力。

区間グラフとは、各頂点に実数上の区間を対応させ、2頂点が辺で結ばれる ⟺ 対応する区間が交差するというグラフ。

制約

パラメータ	範囲
$N$	$1 \le N \le 1000$
$M$	$0 \le M \le N(N-1)/2$

入出力例

入力例 1

出力例 1

YES
1: [1, 3]
2: [2, 4]
3: [3, 5]
4: [4, 6]

入力例 2

出力例 2

NO

入力例2: 4-サイクル（1-2-3-4-1）は弦グラフではないため区間グラフでもない。

概念図: 区間グラフの構造

ヒント（段階的開示）

ヒント1: 方向性

区間グラフは弦グラフ（Chordal Graph）の特殊ケース。まず MCS で PEO を求め弦グラフか確認。弦グラフなら PEO を用いて区間を構成できる。PEO 順に各頂点の右隣接集合が「連続区間」をなすことを確認する。

ヒント2: アプローチ

MCS で PEO $v_1, \ldots, v_N$ を得る
弦グラフ検証: 各 $v_i$ の右隣接集合の最左頂点 $w$ が $R(v_i)\setminus\{w\}$ を全て隣接
区間構成: PEO の逆順に、右隣接集合の最小左端 - 1 を $l_v$ に設定
区間の整合性検証: 全辺が交差、全非辺が非交差

ヒント3: コード骨格

# MCS → PEO
cnt = [0] * (N + 1); visited = [False] * (N + 1); order = []
for _ in range(N):
    v = max(range(1, N+1), key=lambda i: cnt[i] if not visited[i] else -1)
    visited[v] = True; order.append(v)
    for u in adj[v]:
        if not visited[u]: cnt[u] += 1
peo = order[::-1]

# 区間構成
pos = {v: i for i, v in enumerate(peo)}
l_val = {}; r_val = {}; time = 0
for i in range(N-1, -1, -1):
    v = peo[i]
    R = sorted([u for u in adj[v] if pos[u] > i], key=lambda u: pos[u])
    if not R:
        l_val[v] = time; r_val[v] = time; time += 1
    else:
        l_val[v] = min(l_val[u] for u in R) - 1
        r_val[v] = max(r_val[u] for u in R)

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1

    adj = [set() for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        adj[u].add(v)
        adj[v].add(u)

    # MCS で PEO 候補取得 O(N^2)
    cnt = [0] * (N + 1)
    visited = [False] * (N + 1)
    order = []
    for _ in range(N):
        v = -1; best = -1
        for i in range(1, N + 1):
            if not visited[i] and cnt[i] > best:
                best = cnt[i]; v = i
        visited[v] = True
        order.append(v)
        for u in adj[v]:
            if not visited[u]:
                cnt[u] += 1
    peo = order[::-1]

    # 弦グラフ検証
    pos = [0] * (N + 1)
    for i, v in enumerate(peo):
        pos[v] = i

    for i, v in enumerate(peo):
        R = [u for u in adj[v] if pos[u] > i]
        if R:
            w = min(R, key=lambda u: pos[u])
            if not (set(R) - {w}).issubset(adj[w]):
                print("NO")
                return

    # 区間構成（PEO 逆順）
    l_val = [0] * (N + 1)
    r_val = [0] * (N + 1)
    time = 0
    for i in range(N - 1, -1, -1):
        v = peo[i]
        R_right = [u for u in adj[v] if pos[u] > i]
        if not R_right:
            l_val[v] = time
            r_val[v] = time
            time += 1
        else:
            l_val[v] = min(l_val[u] for u in R_right) - 1
            r_val[v] = max(r_val[u] for u in R_right)

    # 区間グラフ検証
    def intersects(u, v):
        return not (r_val[u] < l_val[v] or r_val[v] < l_val[u])

    edge_set = set()
    for v in range(1, N + 1):
        for u in adj[v]:
            if u > v:
                edge_set.add((v, u))

    is_interval = True
    for v in range(1, N + 1):
        for u in range(v + 1, N + 1):
            has_edge = (v, u) in edge_set
            has_intersect = intersects(v, u)
            if has_edge != has_intersect:
                is_interval = False
                break
        if not is_interval:
            break

    if not is_interval:
        print("NO")
    else:
        print("YES")
        for v in range(1, N + 1):
            print(f"{v}: [{l_val[v]}, {r_val[v]}]")

solve()

Step-by-Step 解説

Step 1: 区間グラフの性質

区間グラフは以下と等価:

弦グラフ（Chordal）かつ AT-free（Asteroidal Triple Free）
PEO が存在し、各頂点の右隣接集合が「連続した PEO インデックス範囲」に収まる

Step 2: MCS と弦グラフ

MCS（Maximum Cardinality Search）は貪欲に「訪問済み隣接数が最大の頂点」を選ぶ。逆順が PEO 候補。検証は各 $v_i$ の右隣接集合の最左頂点 $w$ が $R(v_i)\setminus\{w\}$ を全て隣接するかを確認。

Step 3: 区間の構成

PEO の逆順（最後に消去される頂点から）に区間を割り当てる。孤立頂点には新たな座標 $t$ を割り当て、右隣接がある場合は $l[v] = \min(l[R]) - 1$、$r[v] = \max(r[R])$ とする。

Step 4: 検証

構成した区間について全頂点ペアを検査: 辺があるペアは区間が交差し、辺がないペアは区間が交差しないことを確認。$O(N^2)$。

Step 5: 計算量分析

処理	計算量
MCS	$O(N^2)$
PEO 検証	$O(N + M)$
区間構成	$O(N^2)$
整合性検証	$O(N^2)$

よくあるミス

ミス	原因	正しい書き方
弦グラフ = 区間グラフと思う	AT-free 条件も必要	区間の整合性を検証する
区間左端の計算ミス	`min(l[R]) - 1` であることを忘れる	-1 を必ず引く
孤立頂点の処理	右隣接が空の場合、新座標が必要	`time` カウンタで新座標を割り当て
adj を list で持ち issubset が遅い	$O(\|R\| \cdot \|adj\|)$ になる	adj を set で持つ

次のステップ

発展問題: 区間グラフの最大クリーク探索（区間の重なり最大点を求める）
AT-free グラフの認識（Asteroidal Triple の検出 $O(N^3)$）
円形弧グラフ（Circular Arc Graph）への拡張
区間グラフ上の最大独立集合（貪欲法で $O(N \log N)$）

Day 071-Q2 — 区間グラフ認識（Interval Graph Recognition・MCS応用）

問題

制約