📌 题目回顾

  • 有一张有向图，n 个点，m 条边。
  • 每个点要染成 黑 或 白。
  • 一条边 起点黑、终点白 → 称为核心边。
  • 要求构造一种染色，使得核心边数量不少于 m/4（题目保证存在解），并输出所有核心边编号。

📌 思路回顾：条件期望法

  1. 随机染色时，每条边成为核心边的概率 = P(u黑) * P(v白) = 1/2 * 1/2 = 1/4，所以期望核心边数量是 m/4。
  2. 因此一定存在一种确定染色，使核心边数 ≥ m/4。
  3. 做法：依次处理每个点（顺序无所谓）。假设当前点未染色，计算：
  • 如果染成黑：贡献值 = 2 * 已定为白的出边数 + 出边未定数
  • 如果染成白：贡献值 = 2 * 已定为黑的入边数 + 入边未定数取贡献大的方案，定色。更新它的入边/出边统计量。
  • 所有点染色后，再扫一遍所有边，输出符合条件的边编号。

📌 代码

import sys
from sys import stdin

def solve():
    data = stdin.buffer.read().split()
    it = iter(data)
    T = int(next(it))  # 多组测试
    out_lines = []

    for _ in range(T):
        n = int(next(it)); m = int(next(it))

        # 存边信息：eu[i] -> 起点, ev[i] -> 终点
        eu = [0] * (m + 1)
        ev = [0] * (m + 1)

        # 出入邻接表
        outG = [[] for _ in range(n + 1)]
        inG  = [[] for _ in range(n + 1)]

        for i in range(1, m + 1):
            u = int(next(it)); v = int(next(it))
            eu[i], ev[i] = u, v
            outG[u].append(v)
            inG[v].append(u)

        # 初始化统计量
        color    = [-1] * (n + 1)   # -1=未定, 0=黑, 1=白
        decided  = [0] * (n + 1)
        outUndec = [len(outG[i]) for i in range(n + 1)]  # 出边->未定点数
        inUndec  = [len(inG[i])  for i in range(n + 1)]  # 入边<-未定点数
        outWhite = [0] * (n + 1)  # 出边->已定白点数
        inBlack  = [0] * (n + 1)  # 入边<-已定黑点数

        # 条件期望法：顺序处理每个点
        for i in range(1, n + 1):
            # 若染黑：未来贡献= outWhite + 1/2 * 出边未定数
            # 若染白：未来贡献= inBlack + 1/2 * 入边未定数
            # 为什么'1/2'? 
            # 因为未定点的颜色只能是黑色和白色中2选1
            
            # 为了优化运算速度, 直接乘于 2 后比较
            sBlack = 2 * outWhite[i] + outUndec[i]
            sWhite = 2 * inBlack[i] + inUndec[i]

            # 贪心选更优的颜色
            color[i] = 0 if sBlack >= sWhite else 1
            decided[i] = 1

            if color[i] == 0:  # 染黑
                for v in outG[i]:
                    if decided[v] == 0:
                        inUndec[v] -= 1
                        inBlack[v] += 1
                for u in inG[i]:
                    if decided[u] == 0:
                        outUndec[u] -= 1
            else:  # 染白
                for v in outG[i]:
                    if decided[v] == 0:
                        inUndec[v] -= 1
                for u in inG[i]:
                    if decided[u] == 0:
                        outUndec[u] -= 1
                        outWhite[u] += 1

        # 收集所有核心边
        ans = [str(i) for i in range(1, m + 1)
               if color[eu[i]] == 0 and color[ev[i]] == 1]

        out_lines.append(str(len(ans)))
        out_lines.append(' '.join(ans))

    sys.stdout.write('\n'.join(out_lines))


if __name__ == "__main__":
    solve()

📌 复杂度分析

  • 每条边在初始化时加入邻接表 → O(m)
  • 每个点处理时更新入度/出度 → 每条边最多被访问 2 次 → O(m)
  • 整体时间复杂度：O(n + m)，空间复杂度同样 O(n + m)。