迷宫可达任务
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
为了锻炼孩子的胆量，A l i c e AliceAlice和B o b BobBob带着孩子来到一个充满机关的迷宫，迷宫中有n nn间房间，通过m mm条单向通道相连。每次，B o b BobBob会指定两间房间x , y x,yx,y，让孩子在迷宫里从一个房间走到另一个房间。只要孩子能从x xx走到y yy，或能从y yy走到x xx，这个任务就算可完成。为了让每次任务都能无需事先验证可行性，A l i c e AliceAlice希望这个迷宫满足：对任意两间不同的房间x , y x,yx,y，要么x xx可达y yy，要么y yy可达x xx。
【名词解释】
- 可达：如果存在一条沿通道方向的路径，使得从房间u uu能到达房间v vv，则称u uu可达v vv。
- 完美迷宫：对任意不同房间x , y x,yx,y，要么x xx可达y yy，要么y yy可达x xx。
输入描述：
第一行输入两个整数n , m ( 1 ≦ n ≦ 10 5 , 1 ≦ m ≦ 2 × 10 5 ) n, m (1≦n≦10^5, 1≦m≦2×10^5)n,m(1≦n≦105,1≦m≦2×105)，分别表示房间数量和通道数量。
接下来m mm行，每行输入两个整数u , v ( 1 ≦ u , v ≦ n ) u, v (1≦u,v≦n)u,v(1≦u,v≦n)，表示存在一条从房间u uu指向房间v vv的单向通道。
输出描述：
输出一行。如果迷宫为完美迷宫，则输出Y e s YesYes；否则输出N o NoNo。
示例1
输入：
3 3 1 2 2 3 3 1输出：
Yes说明：
在该样例中，房间之间形成环1 → 2 → 3 → 1 1→2→3→11→2→3→1，任意两房间都可互相到达，满足完美迷宫条件。
解题思路
本题核心是强连通分量缩点 + DAG拓扑序唯一性判定，利用强连通分量的内部互达性质，将原图的全域单向可达问题，转化为缩点后有向无环图的链状结构判定。
- 问题等价转化
“任意两点单向可达”的性质可拆解为两部分：
- 每个强连通分量（SCC）内部所有点互相可达，天然满足单向可达要求；
- 缩点后的有向无环图（DAG）必须是一条线性单链，即任意两个SCC之间都存在单向可达关系。此时DAG的拓扑排序结果唯一，每一步都恰好只有一个入度为0的节点。
若DAG中某一步存在多个入度为0的节点，则这些节点之间互相不可达，原图不满足完美迷宫条件。
Tarjan算法求解强连通分量
使用Tarjan算法线性遍历整个有向图，求出所有强连通分量，为每个节点标记所属的分量编号。若整个图只有一个强连通分量（全图强连通），可直接判定为完美迷宫。构建缩点后的DAG
遍历原图所有边，将跨SCC的边转化为缩点之间的边；对缩点边排序去重，避免重复边干扰入度统计，同时统计每个缩点的入度，构建缩点邻接表。拓扑排序校验单链结构
对缩点后的DAG执行拓扑排序：
- 初始将所有入度为0的缩点加入队列；
- 每轮取出队首节点扩展后继节点并减少其入度，若某一时刻队列中节点数大于1，说明存在多个并行的入度0节点，它们之间互相不可达，直接判定不满足条件；
- 若拓扑排序全程队列大小均不超过1，且能遍历所有缩点，则DAG为线性单链，原图是完美迷宫。
算法总时间复杂度为O ( n + m ) O(n + m)O(n+m)，完全适配10万节点、20万边的数据规模。
总结
核心逻辑：通过强连通分量缩点将有向图转化为DAG，再通过拓扑排序过程中入度0节点的数量判断DAG是否为单链，从而验证任意两点单向可达的性质。
关键操作：Tarjan求强连通分量、缩点边去重建图、拓扑排序校验单链性质。
效率保障：全程线性时间复杂度，无嵌套循环，适配十万级节点与边数的运行要求。
代码简要说明
- Tarjan函数：标准强连通分量求解实现，维护
dfn（时间戳）、low（最小可达时间戳）数组，用栈记录当前路径节点；当dfn[u]==low[u]时弹出栈中节点得到一个SCC，标记每个节点所属的分量编号。 - 原图构建：读入节点数与边数，构建原图邻接表；遍历所有节点，对未访问的节点执行Tarjan算法，完成强连通分量划分。
- 缩点建图：遍历原图所有边，筛选跨SCC的边存入列表，排序并去重后构建缩点邻接表，同时统计每个缩点的入度，避免重边导致入度统计错误。
- 拓扑校验：初始化入度为0的缩点入队，BFS执行拓扑排序；若队列大小超过1则直接标记不合法；最终结合合法标记与遍历节点总数判断结果，输出
Yes或No。 - 空间适配：使用vector动态分配数组，适配十万级数据规模，同时关闭流同步加速输入输出。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;vector<vector<ll>>adj;vector<ll>dfn,low,sid;stack<ll>stk;vector<ll>onst;ll tim,sc;voidtarjan(ll u){dfn[u]=low[u]=++tim;stk.push(u);onst[u]=1;for(ll v:adj[u]){if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}elseif(onst[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){++sc;ll v;do{v=stk.top();stk.pop();onst[v]=0;sid[v]=sc;}while(v!=u);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m;cin>>n>>m;adj.assign(n+1,{});for(ll i=0;i<m;i++){ll u,v;cin>>u>>v;adj[u].push_back(v);}dfn.assign(n+1,0);low.assign(n+1,0);sid.assign(n+1,0);onst.assign(n+1,0);tim=0;sc=0;for(ll i=1;i<=n;i++)if(!dfn[i])tarjan(i);if(sc==1){cout<<"Yes"<<endl;return0;}vector<vector<ll>>sadj(sc+1);vector<ll>indeg(sc+1,0);vector<pair<ll,ll>>edges;for(ll u=1;u<=n;u++)for(ll v:adj[u])if(sid[u]!=sid[v])edges.push_back({sid[u],sid[v]});sort(edges.begin(),edges.end());edges.erase(unique(edges.begin(),edges.end()),edges.end());for(auto&e:edges){sadj[e.first].push_back(e.second);indeg[e.second]++;}queue<ll>q;for(ll i=1;i<=sc;i++)if(!indeg[i])q.push(i);ll cnt=0;boolok=true;while(!q.empty()){if(q.size()>1){ok=false;break;}ll u=q.front();q.pop();cnt++;for(ll v:sadj[u]){indeg[v]--;if(!indeg[v])q.push(v);}}if(ok&&cnt==sc)cout<<"Yes"<<endl;elsecout<<"No"<<endl;return0;}
