题目理解

我们有 $n$ 个国家和 $n$ 个名次，每个记者报道自己国家选手的名次：

• 确定报道：T a - 名次一定是 $a$
• 不确定报道：N a b - 名次是 $a$ 或 $b$

需要判断是否能唯一确定排名，或者计算可能的排名数量。

关键观察

1. 图论建模

将名次视为节点，每个不确定报道 N a b 在名次 $a$ 和 $b$ 之间连一条边。这样形成一个图，每个连通分量代表一组相互关联的名次。

2. 约束分析

• 每个连通分量有 $p$ 个节点（名次）和 $e$ 条边（不确定报道）
• 如果 $e > p$：约束过多，出现矛盾
• 如果 $e = p$：形成基环树，有 2 种分配方式（选择环的方向）
• 如果 $e < p$：有唯一确定解

算法核心

并查集维护连通分量

for (int i = 1; i <= n; i++)
    fa[i] = i, p[i] = 1;  // 初始化并查集

for 每个报道:
    if "T":
        ++e[find(x)];      // 增加约束计数
        h[find(x)] = i;    // 记录确定报道
    else "N a b":
        // 在a和b之间建边
        g[a].push_back({b, i});
        g[b].push_back({a, i});
        
        // 合并连通分量
        int fx = find(a), fy = find(b);
        if (fx == fy)
            e[fx]++;       // 同分量内增加边
        else {
            fa[fx] = fy;
            p[fy] += p[fx];  // 合并节点数
            e[fy] += e[fx] + 1;  // 合并边数
            h[fy] |= h[fx];  // 合并确定报道标记
        }

可行性判断

for 每个连通分量i:
    if e[i] > p[i]:   // 约束过多，矛盾
        cout << "NIE\n0\n";
        return;
    else if e[i] == p[i]:  // 基环树，有2种选择
        if !h[i]:          // 没有确定报道
            ans = ans * 2 % P, one = 0;

构造唯一解

当所有连通分量都满足 $e < p$ 或有确定报道时：

for 每个连通分量i:
    int x = h[i];      // 确定报道
    cho[x] = u[x];     // 固定选择
    dfs(u[x], 0);      // 深度优先遍历确定其他选择

算法正确性

1. 图论模型正确性

• 节点：名次
• 边：不确定报道连接的两个可能名次
• 连通分量：相互关联的名次集合

2. 约束分析正确性

• $e > p$：类似于有 $p$ 个变量但超过 $p$ 个独立方程，必然矛盾
• $e = p$：基环树结构，环有两种定向方式
• $e < p$：树结构，从确定报道出发可以唯一确定

3. 构造算法正确性

从确定报道出发进行DFS，可以唯一确定连通分量内所有选择。

时间复杂度

• 并查集操作：$O(n \alpha(n))$
• DFS遍历：$O(n)$
• 总复杂度：$O(n \alpha(n))$

在 $n \leq 10^6$ 的限制下完全可行。

关键数据结构

1. 并查集：维护连通分量
2. 邻接表：g[N] 存储图结构
3. 统计数组：
   • p[i]：连通分量节点数
   • e[i]：连通分量边数
   • h[i]：连通分量中是否有确定报道

算法优势

1. 图论建模：将排名问题转化为图论问题
2. 分量分析：独立处理每个连通分量
3. 高效判断：通过简单计数判断唯一性
4. 构造算法：需要时能高效构造解

算法标签

• 并查集
• 图论
• 连通分量
• 组合计数

特殊情况处理

确定报道的作用

确定报道 T a 在连通分量中：

• 增加约束计数 $e$
• 标记该分量有确定信息
• 当 $e = p$ 时，有确定报道则解唯一，否则有2种可能

矛盾检测

任何连通分量出现 $e > p$ 立即判定矛盾，输出0种可能。

总结

该算法通过巧妙的图论建模和并查集维护，将复杂的排名确定问题转化为连通分量的约束分析。核心思想是利用图的结构性质判断解的唯一性，并通过组合计数计算可能方案数。算法设计简洁高效，充分体现了图论在组合问题中的应用价值。