迷宫城堡

题目解析

模板题目, 求scc的数量

这是一个非常经典的强连通分量（SCC）练习题。

核心要求：题目要求判断图中“任意两个房间是否相互连通”。
数学定义：在有向图中，如果图中任意两个点 $u$ 和 $v$ 都可以互相到达，那么这个图被称为强连通图 (Strongly Connected Graph)。
判定方法：
- 利用 Tarjan 算法求出图中所有的强连通分量（SCC）。
- 如果整个图只有一个强连通分量（即 scc_cnt == 1），且这个分量包含了所有的 $N$ 个顶点，那么这个图就是强连通的。
- 否则，输出 “No”。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2025-12-29 10:32:04
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
const int maxe = 4e6+5;
const int mod = 1e9+7;

int n,m;
int a[maxn];


struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }
    void reset() {
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    //下标访问
    edge& operator[](int i){ return e[i]; }
    //返回head[u]
    int operator()(int u){ return h[u]; }
} e;

//oisnip_beginscc.cpp
struct TarjanScc {
    int n, timer;
    std::stack<int> st;
    bool in_stack[maxn];
    int dfn[maxn], low[maxn], scc_id[maxn];
    int scc_cnt; // SCC 的总数

    TarjanScc(int _n) {
    }
    void set(int _n){
        n = _n;
        timer = scc_cnt = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(in_stack, 0, sizeof(in_stack));
    }

    // 有向图,不要加father参数
    void dfs(int u) {
        dfn[u] = low[u] = ++timer;
        st.push(u);
        in_stack[u] = true;

        for (int i = e(u); ~i ; i = e[i].next) {
            int v = e[i].v;
            if (!dfn[v]) { // 如果 v 没被访问过
                dfs(v);
                
                // 根据子节点的 low 值更新当前节点的 low 值
                low[u] = std::min(low[u], low[v]);
            } else if (in_stack[v]) { //返祖边, 如果 v 在栈中，说明构成了环
                low[u] = std::min(low[u], dfn[v]);
            }
        }

        // 如果 dfn == low，说明找到了一个 SCC 的起始点
        if (low[u] == dfn[u]) {
            scc_cnt++;
            while (1) {
                int v = st.top(); st.pop();
                in_stack[v] = 0;
                scc_id[v] = scc_cnt; // 标记所属 SCC 编号
                if (v == u) break; // 直到找到起始点
            }
        }
    }

    void solve() {
        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) dfs(i);
        }
    }
};
//oisnip_end

TarjanScc tj(1);


void init(){

}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);

    while (1) {
        e.reset();
        std::cin >> n >> m;
        if( n == 0 && m == 0) break;
        for(int i = 1;i <= m ;++i ) // i: 1->m
        {
            int u,v;
            std::cin >> u >> v;
            e.add(u,v);
        }
        tj.set(n);
        tj.solve();
        if( tj.scc_cnt == 1)
            std::cout << "Yes" << "\n";
        else
            std::cout << "No" << "\n";
        
    }
    
    return 0;
}

目录

题目解析

代码