P12746 [POI 2016 R3] 非凡旅行 Amusing journeys

题目大意

给出一张 $n$ 个点、$m$ 条边的无向连通图。定义“非凡旅行”为一个至少包含一条边的简单回路（不重复经过任何城市，也不重复经过任何铁路）。

• 若存在非凡旅行，且所有旅行的长度都相同，则输出 TAK，并输出旅行长度和数量（数量对 $10^9+7$ 取模）；
• 若存在非凡旅行但长度不全都相同，则输出 NIE；
• 若不存在非凡旅行，则输出 BRAK。

错误思路

最初容易想到用 Tarjan 求出所有点双连通分量，并且认为每个点数 $\ge 3$ 的点双就是一个简单环，环长等于点数（边数），贡献为 $2 \times \text{点数}$（因为可以从任意一点出发，顺时针或逆时针各算一种）。检查所有环长是否相等后直接输出。

然而这种写法会 WA。原因在于存在一种特殊的点双——$\Theta$ 图，它并不是简单环，但内部所有简单环的长度却可能相等。如果简单地将所有 $\Theta$ 图拆成不同的环，就会错误地判断为环长不一致。

正确解法

结论

点数 $\ge 3$ 的点双，满足“所有简单环长度相等”当且仅当它是以下两种形态之一：

1. 简单环：所有顶点度数恰好为 $2$，且边数等于点数。
2. $\Theta$ 图：恰好有两个度数 $>2$ 的顶点，其余顶点度数全部为 $2$；并且这两个高度数顶点（称为枢纽）之间的每一条路径长度都相等。

算法流程

1. 对所有未访问的点运行 Tarjan，求出所有点双（同时得到点集和边集）。
2. 遍历每一个点双，进行如下判断：
   • 若点数 $<3$，直接忽略（不构成环）。
   • 统计点双内部每个点的度数（仅考虑该点双内部的边）。
   • 若所有点度数 $=2$：简单环，环长 $L = \text{点数}$，贡献为 $2L$。
   • 若有两个点度数 $>2$，且其余点度数 $=2$：可能是 $\Theta$ 图。设这两个特殊点为 $A$ 和 $B$，度数均为 $k$。在分量内部从 $A$ 的每个邻居出发，沿着度数全为 $2$ 的路径走到 $B$，记录每条路径的长度。若所有路径长度相等，则合法；环长 $L = 2 \times \text{路径长度}$，贡献为 $k(k-1) \times L$。
   • 否则（点数 $\ge 3$ 且不符合以上任一情况），直接输出 NIE。
3. 检查所有合法点双的环长是否全部相等。若不等，输出 NIE；若不存在任何合法环，输出 BRAK；否则输出 TAK 以及环长和总旅行数。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lpx 1000005
#define mod 1000000007
ll n,m,low[lpx],dfn[lpx],sta[lpx],num,tot,etop;
pair<ll,ll>pai[lpx];
ll ans=0,pan=0;
bool check=false;
vector<ll>linker[lpx];
// 全局临时变量，用于存储当前点双的点集、边集
vector<ll> nodes;
vector<pair<ll,ll>>paii;
unordered_map<ll,ll> deg;            // 点双内各点的度数
unordered_map<ll, vector<ll>> adj;   // 点双内部的邻接表
vector<ll> lens;                      // Θ图中每条路径的长度
// 处理一个点双连通分量
void checkk(){
    ll sz = nodes.size();
    if(sz < 3) return;               // 点数 < 3 无法形成环，直接跳过
    // 1. 统计点双内各点的度数（仅考虑该点双内部的边）
    deg.clear();
    for(auto &e :paii){
        deg[e.first]++;
        deg[e.second]++;
    }
    // 2. 分类：统计度数 >2 的点，记录特殊点
    ll cnt_gt2 = 0;
    ll hub1 = -1, hub2 = -1;
    for(auto &p : deg){
        ll d = p.second;
        if(d > 2){
            cnt_gt2++;
            if(cnt_gt2 == 1) hub1 = p.first;
            else if(cnt_gt2 == 2) hub2 = p.first;
        } else if(d != 2){           // 度数既不是 2 也不是 >2，只能是 1，非法
            puts("NIE"); exit(0);
        }
    }
    // 情况一：所有点度数均为 2,即为简单环
    if(cnt_gt2 == 0){
        ll L = sz;
        if((ll)nodes.size()!=sz){    // 边数应等于点数
            puts("NIE"); exit(0);
        }
        // 检查全局环长是否一致
        if(!check){
            check = true;
            pan = L;
        } else if(pan != L){
            puts("NIE"); exit(0);
        }
        ans = (ans + 2LL * L) % mod; // 贡献 2L 条不同旅行
    }
    // 情况二：恰好两个度数 >2 的点 → 可能是 Θ 图
    else if(cnt_gt2 == 2){
        ll k = deg[hub1];
        if(deg[hub2] != k){          // 两个枢纽的度数必须相等
            puts("NIE"); exit(0);
        }
        // 构建点双内部的临时邻接表
        adj.clear();
        for(auto &e :paii){
            adj[e.first].push_back(e.second);
            adj[e.second].push_back(e.first);
        }
        // 遍历 hub1 的每条出边，计算到 hub2 的路径长度
        lens.clear();
        for(ll nxt:adj[hub1]){
            ll cur = nxt, prev = hub1;
            ll len = 1;
            while(cur != hub2){
                ll nxt_node = -1;
                // 中间点度数必为 2，只需找到非 prev 的邻居
                for(ll nb : adj[cur])
                    if(nb != prev) { nxt_node = nb; break; }
                if(nxt_node == -1){ puts("NIE"); exit(0); }
                prev = cur;
                cur = nxt_node;
                len++;
            }
            lens.push_back(len);
        }
        // 所有路径长度必须相等
        for(ll l : lens) if(l != lens[0]){ puts("NIE"); exit(0); }
        
        ll len = lens[0];
        ll L = 2 * len;                      // 环长 = 路径长度 × 2
        ll cnt_cycles = (ll)k * (k-1) % mod; // k(k-1)
        cnt_cycles = cnt_cycles * L % mod;   // × L 得到旅行总数
        
        // 检查全局环长是否一致
        if(!check){
            check = true;
            pan = L;
        } else if(pan !=L){
            puts("NIE");exit(0);
        }
        ans = (ans+cnt_cycles) % mod;
    }
    // 情况三：度数 >2 的点超过两个 → 非法
    else {
        puts("NIE"); exit(0);
    }
}
// Tarjan 算法求点双连通分量
void tar(ll u,ll fa){
    low[u]=dfn[u]=++tot;           // 时间戳
    sta[++num]=u;                   // 顶点入栈
    for(auto v:linker[u]){
        if(v==fa) continue;
        if(!dfn[v]){                // 树边
            pai[++etop]={u,v};      // 边入栈
            tar(v,u);
            low[u]=min(low[u],low[v]);
            
            if(low[v]>=dfn[u]){     // 发现一个点双（u 是割点或根）
                nodes.clear();
                paii.clear();
                nodes.push_back(u); // 割点 u 属于该点双
                ll y;
                do{                 // 弹出点栈中的点
                    y=sta[num--];
                    nodes.push_back(y);
                }while(y!=v);
                
                pair<ll,ll> e;
                do{                 // 弹出边栈中的边
                    e=pai[etop--];
                    paii.push_back(e);
                }while(!(e.first==u && e.second==v));
                
                checkk();           // 处理该点双
            }
        }
        else{                        // 返祖边
            if(dfn[v] < dfn[u])      // 保证每条边只入栈一次
                pai[++etop] = {u, v};
            low[u]=min(low[u],dfn[v]);
        }
    }
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1,a,b;i<=m;++i){
        scanf("%lld%lld",&a,&b);
        linker[a].push_back(b);
        linker[b].push_back(a);
    }
    // 对每个未访问的连通分量运行 Tarjan
    for(ll i=1;i<=n;++i){
        if(!dfn[i]){
            num=0; etop=0;
            tar(i,0);
            // 处理根节点所在点双（栈中剩余元素）
            if(num > 0){
                nodes.clear();
                paii.clear();
                for(ll j=1;j<=num;++j) nodes.push_back(sta[j]);
                for(ll j=1;j<=etop;++j)paii.push_back(pai[j]);
                checkk();
                num=0; etop=0;
            }
        }
    }
    if(!check)
        puts("BRAK");               // 不存在任何非凡旅行
    else{
        puts("TAK");                // 所有非凡旅行长度相同
        printf("%lld %lld",pan,ans);
    }
    return 0;
}