迷宫可达任务时间限制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(nm)完全适配10万节点、20万边的数据规模。总结核心逻辑通过强连通分量缩点将有向图转化为DAG再通过拓扑排序过程中入度0节点的数量判断DAG是否为单链从而验证任意两点单向可达的性质。关键操作Tarjan求强连通分量、缩点边去重建图、拓扑排序校验单链性质。效率保障全程线性时间复杂度无嵌套循环适配十万级节点与边数的运行要求。代码简要说明Tarjan函数标准强连通分量求解实现维护dfn时间戳、low最小可达时间戳数组用栈记录当前路径节点当dfn[u]low[u]时弹出栈中节点得到一个SCC标记每个节点所属的分量编号。原图构建读入节点数与边数构建原图邻接表遍历所有节点对未访问的节点执行Tarjan算法完成强连通分量划分。缩点建图遍历原图所有边筛选跨SCC的边存入列表排序并去重后构建缩点邻接表同时统计每个缩点的入度避免重边导致入度统计错误。拓扑校验初始化入度为0的缩点入队BFS执行拓扑排序若队列大小超过1则直接标记不合法最终结合合法标记与遍历节点总数判断结果输出Yes或No。空间适配使用vector动态分配数组适配十万级数据规模同时关闭流同步加速输入输出。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;vectorvectorlladj;vectorlldfn,low,sid;stackllstk;vectorllonst;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{vstk.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;cinnm;adj.assign(n1,{});for(ll i0;im;i){ll u,v;cinuv;adj[u].push_back(v);}dfn.assign(n1,0);low.assign(n1,0);sid.assign(n1,0);onst.assign(n1,0);tim0;sc0;for(ll i1;in;i)if(!dfn[i])tarjan(i);if(sc1){coutYesendl;return0;}vectorvectorllsadj(sc1);vectorllindeg(sc1,0);vectorpairll,lledges;for(ll u1;un;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(autoe:edges){sadj[e.first].push_back(e.second);indeg[e.second];}queuellq;for(ll i1;isc;i)if(!indeg[i])q.push(i);ll cnt0;booloktrue;while(!q.empty()){if(q.size()1){okfalse;break;}ll uq.front();q.pop();cnt;for(ll v:sadj[u]){indeg[v]--;if(!indeg[v])q.push(v);}}if(okcntsc)coutYesendl;elsecoutNoendl;return0;}