迷宫城堡+算法讲解【tarjian算法】

Tarjan 算法

参考博客：https://www.cnblogs.com/shadowland/p/5872257.html

算法讲解

Tarjan 算法一种由Robert Tarjan提出的求解有向图强连通分量的算法，它能做到线性时间的复杂度。

强连通定义：

如果两个顶点可以相互通达，则称两个顶点强连通：

例如：下图中 1 3 两点强联通

1→3

3→4→1 类似1 3 两点称为强连通

如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

例如：在上图中，{1 , 2 , 3 , 4 } , { 5 }　, { 6 } 三个区域可以相互连通，称为这个图的强连通分量。

Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

再Tarjan算法中，有如下定义。

DFN[ i ] : 在DFS中该节点被搜索的次序(时间序号)

LOW[ i ] : 为i或i的子树能够追溯到的最早的栈中节点的次序号

当DFN[ i ]==LOW[ i ]时，为i或i的子树可以构成一个强连通分量。

二.算法图示（链式前向星存图）

以1为Tarjan 算法的起始点，如图：

顺次DFS搜到节点6

回溯时发现LOW[ 5 ]==DFN[ 5 ] , LOW[ 6 ]==DFN[ 6 ] ,则{ 5 } , { 6 } 为两个强连通分量。回溯至3节点，拓展节点4.

拓展节点1 ，发现1再栈中更新LOW[ 4 ]，LOW[ 3 ] 的值为1

回溯节点1，拓展节点2

自此，Tarjan Algorithm 结束，{1 , 2 , 3 , 4 } , { 5 }　, { 6 } 为图中的三个强连通分量。

不难发现，Tarjan Algorithm 的时间复杂度为O(E+V).

例题：

迷宫城堡

为了训练小希的方向感，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

Sample Output

Yes

思路：

根据题目可以知道要想判断房间是否可以全部相互连通也就可以想到是强连通（判断是不是全体属于一个scc值）就可以解决，开始是用for循环判断全部的值是不是相等，后来看同学代码知道只要判断最后sig是不是为1（也就是sig只是++了一次）。还有就是题目是多组输入，所以每次在输入之前都要为链式前向星做准备（head[i]=-1）和 memset所有数组。

AC代码：

用链式前向星存图

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5;
struct node{
    int to;
    int next;
}edge[MAX+5];
int n,m;
int head[MAX+5],ans;
void addnode(int u,int v)
{
    edge[ans].to=v;
    edge[ans].next=head[u];
    head[u]=ans++;
}
void allbegin()
{
    memset(head,-1,sizeof(head));
    ans=0;
}
int dfn[MAX+5];
int low[MAX+5],num;
int sta[MAX+5],top;
int scc[MAX+5],sig;

void dfs(int u)
{
    dfn[u]=low[u]=++num;
    sta[top++]=u;    //进栈
    for(int i=head[u];~i;i=edge[i].next){
        int t=edge[i].to;
        if(dfn[t]==0){      //深搜
            dfs(t);    
            low[u]=min(low[u],low[t]);
        }
        else if(scc[t]==0){
            low[u]=min(low[u],low[t]);
        }
    }
    if(dfn[u]==low[u]){  //将可以强连通的点附上相同的值 表示属于相同的一个强连通图
        sig++;
        while(1){
            int j=sta[--top];  //top表示存入了多少点（从0开始，所以--top）
            scc[j]=sig;
            if(j==u){
                break;
            }
        }
    }
}

void tarjian()
{
    sig=0,top=0,num=0;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(sta,0,sizeof(sta));
    memset(scc,0,sizeof(scc));
    for(int i=1;i<=n;i++){
        if(dfn[i]==0){     //从每一个点出发
            dfs(i);
        }
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m)){
        if(n==0&&m==0){
            break;
        }
        else{
            allbegin();  //链式前向星准备
            for(int i=1;i<=m;i++){
                int u,v;
                scanf("%d%d",&u,&v);
                addnode(u,v);
            }
            tarjian();
            if(sig==1){
                printf("Yes
");
            }
            else{
                printf("No
");
            }
        }
    }
    return 0;
}