hdu 1269 迷宫城堡 (Kosaraju+缩点)

题目链接: hdu 1269

题目大意: 给出的有向图是否满足任意两点a,b之间

存在a到b的路径和b到a的路径

解题思路: 判断是否仅有一个强联通分量

Kosaraju算法的核心思想：

从未访问过的点用Kosaraju正向边搜索遍历完所有的顶点，记录层次dnf[ ]

然后按照深度优先搜索层次从小到大顺序再搜索一次反向边

若是图G‘强联通分量，无论正向边还是反向边搜索任意两个顶点能互相到达

若不是，则正向搜索无法到达或者逆向搜索无法到达

Kosaraju算法的执行过程:

1.对原图G进行深度优先搜索，并记录每个顶点的dnf值；

2.将图G的割边进行反向，得到其逆图GT；

3.选择从当前dnf值最小的顶点出发，对逆图GT进行DFS搜索，删除能够遍历到的顶点

这些顶点构成一个强联通分量；

4.如果还有顶点没有删除，继续执行第(3)步，否则算法结束.

代码:

//Final   kosaraju判断有向图是否为强联通图  
#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
#define MAX 10100  
struct snode{  
    int to,next;  
}edge1[MAX*30],edge2[MAX*30],edge3[MAX*30];  
int visit1[MAX],In[MAX],To[MAX],pre1[MAX],pre2[MAX],Index1,Index2,k,list[MAX];  
int father[MAX];  
void Add_edge1(int a,int b)  //建立正向图  
{  
    edge1[Index1].to=b,edge1[Index1].next=pre1[a];  
    pre1[a]=Index1++;  
}  
  
void Add_edge2(int a,int b)  //建立逆向图  
{  
    edge2[Index2].to=b,edge2[Index2].next=pre2[a];  
    pre2[a]=Index2++;  
}  
  
void Kosaraju(int u)     //第一次正向图搜索  
{  
    int i,v;  
    for(i=pre1[u];i!=-1;i=edge1[i].next)  
    {  
        v=edge1[i].to;  
        if(visit1[v]==0)  
        {  
            visit1[v]=1;  
            Kosaraju(v);  
        }  
    }  
    list[k++]=u;  
}  
  
void DFS(int u,int Father)   //第二次逆向图搜索  
{  
    int i,v;  
    visit1[u]=2;  
    father[u]=Father;  
    for(i=pre2[u];i!=-1;i=edge2[i].next)  
    {  
        v=edge2[i].to;  
        if(visit1[v]==1)  
            DFS(v,Father);  
    }  
}  
  
int main()  
{  
    int n,m,i,j,a,b,c,pd;  
    while(scanf("%d%d",&n,&m)!=EOF)  
    {  
        if(n==0&&m==0)  
            break;  
        Index1=Index2=0;  
        memset(In,0,sizeof(In));  
        memset(pre1,-1,sizeof(pre1));  
        memset(pre2,-1,sizeof(pre2));  
        memset(visit1,0,sizeof(visit1));  
        memset(father,0,sizeof(father));  
        for(i=0;i<m;i++)  
        {  
            scanf("%d%d",&a,&b);  
            Add_edge1(a,b);  
            Add_edge2(b,a);  
        }  
        for(i=1,k=0;i<=n;i++)  
        {  
            if(!visit1[i])  
            {  
                visit1[i]=1;  
                Kosaraju(i);  
            }  
        }  
        for(j=k-1,c=0;j>=0;j--)    //第二次搜索和第一次搜索顶点的顺序一样  
        {  
            if(visit1[list[j]]==1)  
            {  
                DFS(list[j],++c);  
            }  
        }  
        for(i=1,pd=0;i<n;i++)   //有两个联通块就说明不是联通图  
            if(father[i]!=father[i+1])  
                pd=1;  
        if(pd==0)  
            printf("Yes\n");  
        else  
            printf("No\n");  
    }  
    return 0;  
}

补充：软件开发 , C++ ,