HDU 1269 迷宫城堡 (强连通分量裸题)

题目

Problem Description
为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。

Input
输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。

Output
对于输入的每组数据，如果任意两个房间都是相互连接的，输出"Yes"，否则输出"No"。

Sample Input
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0

Sample Output
Yes
No

Author
Gardon

Source
HDU 2006-4 Programming Contest

思路

强连通分量的板子题，但是因为不会tarjan，强连通一律两边dfs狗头保命。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int st[3][maxn<<1],to[3][maxn],nxt[3][maxn];
int topt,n,m,vis[maxn];
int cnt,q[maxn],f[maxn];
int Scnt;
inline void add_edge (int u,int v) {
    to[0][++topt]=v; nxt[0][topt]=st[0][u]; st[0][u]=topt;
    to[1][topt]=u; nxt[1][topt]=st[1][v]; st[1][v]=topt;
}

void dfs1 (int x) {
    vis[x]=1;
    int p=st[0][x];
    while (p) {
        if (!vis[to[0][p]]) dfs1 (to[0][p]);
        p=nxt[0][p];
    }
    q[++cnt]=x;
    return ;
}

void dfs2 (int x,int Scnt) {
    vis[x]=0; f[x]=Scnt;
    int p=st[1][x];
    while (p) {
        if (vis[to[1][p]]) dfs2 (to[1][p],Scnt);
        p=nxt[1][p];
    }
    return ;
}

void init () {
    topt=0; memset (st,0,sizeof (st));
    memset (vis,0,sizeof (vis)); Scnt=0; cnt=0;
}

int main () {
    while (scanf ("%d%d",&n,&m)) {
        if (n==0&&m==0) break;
        init ();
        for (int i=1;i<=m;i++) {
            int a,b;
            scanf ("%d%d",&a,&b);
            add_edge (a,b);
        }
        for (int i=1;i<=n;i++) if (!vis[i]) dfs1 (i);
        for (int i=n;i;i--) if (vis[q[i]]) dfs2 (q[i],++Scnt);
        if (Scnt==1) printf ("Yes
");
        else printf ("No
");
    }
    return 0;
}