POJ_2762_强连通分量

刚刚在算导上学会用两次dfs求SCC,终于过了前段时间群赛的一个题。

http://poj.org/problem?id=2762

题意：给定一个有向图，让你求它是否为半连通图（即对于图中任意两个顶点u,v 是否有u可以到达v或者v可以到达u）

解题思路：当时还不知道啥强连通分量，看了人家的一篇博客，了解了下解题思路，就是先求强连通分量+缩点，得到缩点以后的DAG（有向无环图），然后对缩点以后的图进行拓扑排序，如果有分叉则说明，原图不是半连通的（即从分叉处往下的两个分支，不能保证对于其中任意两个节点之间可达）。

关于该算法的正确性，算导上面证明的很清楚。

求SCC的步骤为：
1. 对原图进行dfs，求出每个结点的离开时间。

2. 按离开时间从后到前，对逆图进行dfs,每次dfs所到达的结点就组成一个强连通分量。（其实每个强连通分量可以看成一个点，然后这些点能构成一个DAG，至于如何保持SCC构成的DAG，其实可以用一个belong数组，belong[v]表示v结点属于哪一个强连通分量，这样在进行第二次dfs的时候如果搜索到已经被访问过的点上，并且该点在已经求出的强连通分量上，那么就把scc[belong[w]][now]置1,表示以前求出的强连通分量到当前正在求的强连通分量有一条边，不过我这里没想到这个好办法，我是把每个强连通分量里包含的顶点保存下来，如果搜索到已经访问过的结点就去以前求出的强连通分量里找该结点如果找到就在scc中添加一条边）

按上述顺序求出缩点以后的图,进行拓扑排序：

1. 每次取出所有结点中入度为0的并且没有被访问过的结点，如果这样的结点有多个，说明存在分支，则输出NO

2. 如果所有结点能按照1步骤进行排序，说明没有分支，则输出YES.

代码如下：

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1001;
int scc[MAXN][MAXN],vis[MAXN],f[MAXN],indeg[MAXN],scccnt;
vector<int> sccv[MAXN],g[MAXN],gt[MAXN];
bool find(int w,int i)
{
     for(int j=0;j<sccv[w].size();j++)
     if(sccv[w][j]==i)return true;
     return false;
}
void dfs1(int v,int &time,int n)//cac the f array
{
     vis[v] = 1;
     for(int i=0;i<g[v].size();i++)
     {
         if(!vis[g[v][i]])dfs1(g[v][i],time,n);
     }
     f[time++] = v;
}
void dfs2(int v,int n)//mark one scc
{
     vis[v] = 1;
     sccv[scccnt].push_back(v);//the set of the scc's vertex 
     for(int i=0;i<gt[v].size();i++)
     {
             if(!vis[gt[v][i]])
             dfs2(gt[v][i],n);
             else
             {
                 for(int j=scccnt-1;j>=0;j--)
                 {
                     if(find(j,gt[v][i]))//if find the scc which contain the vertex 
                     {
                         scc[j][scccnt] = 1;//mark the scc graph
                     }
                 }
             }
     }
}
void SCC(int n)//cac all scc
{
     for(int i=0;i<MAXN;i++)
     sccv[i].clear();
     memset(vis,0,sizeof(vis));
     int time = 0;scccnt = 0;
     for(int i=1;i<=n;i++)
     {
         if(!vis[i])dfs1(i,time,n);
     }
     memset(vis,0,sizeof(vis));
     memset(scc,0,sizeof(scc));
     for(int i=time-1;i>=0;i--)
     {
         if(!vis[f[i]])
         {
             dfs2(f[i],n);
             scccnt++;
         }
     }
}
bool solve()//toposort
{
     memset(indeg,0,sizeof(indeg));
     for(int i=0;i<scccnt;i++)
     {
         for(int j=0;j<scccnt;j++)
         {
             if(scc[j][i])indeg[i]++;
         }
     }//cac indegree
     memset(vis,0,sizeof(vis));
     //toposort
     for(int i=0;i<scccnt;i++)
     {
         int cnt=0,v=-1;
         for(int j=0;j<scccnt;j++)
         {
             if(indeg[j]==0&&!vis[j])
             {
                 cnt++;
                 v = j;
             }
         }
         if(cnt!=1)return false;
         vis[v] = 1;
         for(int j=0;j<scccnt;j++)//update indegree
         {
             if(scc[v][j])indeg[j]--;
         }
     }
     return true;
}
int main()
{
    int n,t,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++)
        g[i].clear(),gt[i].clear();
        for(int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
            gt[b].push_back(a);
        }
        SCC(n);
        bool ok = solve();
        if(ok) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}