暑期集训——SCC

 

有向图的强连通分量(SCC

对于一个有向图,有点u到点v可达,不一定意味着vu可达,对于一个有向图,如果任意两点间都相互可达,则该图称为一个强连通图。若任意两点间要么u可达v,要么v可达u则称该图为单侧连通图。若去掉有向图的方向后为一个连通图则为弱连通图。对于一个图,若其不是强连通图,但是总可以找到它的连通分量,使得联通分量的点都是相互可达的,对于极大的连通分量即为图的强连通分量(Strongly Connected Component, SCC),类似的有图的单侧连通分量,和弱连通分量。求一个图的弱连通分量,只需要用dfs或者bfs对图做一下遍历即可,有几棵树就有几个弱连通分量。对于求单侧连通分量,????。对于求有向图的强连通分量有以下算法:

1.      对有向图以某个节点做dfs记录各点的结束时间。

2.      将图所有边反向,以结束时间从大到小,再做一遍dfs,如果从某个点可以遍历到一些点,则这些点可以构成一个强连通分量。

SCC求强连通分量的伪代码(邻接表表示,且同时完成了缩点操作,缩点时一般还需要对一些量进行特殊设定,需要在缩点时进行修改,该题是缩点时记录新节点包括旧图中的几个节点。)

vector<int>v1[MAX]; //原图
vector<int>v2[MAX]; //反向边图
int mark[MAX],Stack[MAX];
int Num[MAX],Nn[MAX];
int dep;
void dfs1(int i)
{
   mark[i]
=1;
   
for(int j=0;j<v1[i].size();j++)
      
if(!mark[v1[i][j]])
      dfs1(v1[i][j]);
   Stack[dep
++]=i;   
}

void dfs2(int i)
{
   Num[i]
=cnt;
   Nn[cnt]
++;
   mark[i]
=1;
   
for(int j=0;j<v2[i].size();j++)
      
if(!mark[v2[i][j]])
      dfs2(v2[i][j]);      
}

void scc()//两边dfs
{
   
int i,j;
   dep
=1;
   memset(mark,
0,sizeof(mark));
   
for(i=1;i<=n;i++)
      
if(!mark[i])
      dfs1(i);
   memset(mark,
0,sizeof(mark));
   cnt
=0;
   
for(i=n;i>0;i--)
      
if(!mark[Stack[i]])
      
{
         cnt
++;
         dfs2(Stack[i]);
      }

}

posted on 2010-07-12 18:51 YUANZX 阅读(709) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年7月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜