HDU 1269 迷宫城堡【有向图的强连通分量，Kosaraju算法】

参考：《算法竞赛 入门到进阶》P232

HDU 1269 迷宫城堡

Kosaraju算法求有向图强连通分量，时间复杂度$O(V+E)$。

两次dfs，第一次按原图dfs，用个vector数组存储dfs序；
第二次按反图（所有边反向）dfs，第一次dfs序大的（第一次dfs后搜到的）先搜索，然后把每个点记录其强连通分量的编号。

本题要求有向图中任意两个点都连通，即整个图中强连通分量个数为1。

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10;
int n,m,cnt,scc[N];
vector<int>g[N]; // 原图
vector<int>rg[N];// 反图
vector<int>s; // 按原图dfs序存储
bool vis[N];
void dfs1(int u)
{
    if(vis[u])return;vis[u]=1;int sz=g[u].size();for(int i=0;i<sz;i++)dfs1(g[u][i]);s.push_back(u);
}
void dfs2(int u)
{
    if(scc[u])return;scc[u]=cnt;int sz=rg[u].size();for(int i=0;i<sz;i++)dfs2(rg[u][i]);
}
bool judge()
{
    memset(vis,0,sizeof(vis));memset(scc,0,sizeof(scc));s.clear();cnt=0;for(int i=1;i<=n;i++)if(!vis[i])dfs1(i);for(int i=n-1;i>=0;i--) // 从dfs序大的点搜索它的强连通分量{
    int u=s[i];if(!scc[u]){
    cnt++;if(cnt>1)return 0;dfs2(u);}}return cnt==1;
}
int main()
{
    ios::sync_with_stdio(false);while(cin>>n>>m&&!(n==0&&m==0)){
    for(int i=1;i<=n;i++){
    g[i].clear();rg[i].clear();}int x,y;for(int i=1;i<=m;i++){
    cin>>x>>y;g[x].push_back(y);rg[y].push_back(x);}if(judge())printf("Yes\n");else printf("No\n");}return 0;
}