思路模糊时看了DieIng大牛的思路,写了出来...
思路:Tarjan算法计算强连通分支,然后缩点,再求其拓扑序。
(假设求得的拓扑序存储在topo[MAX]中) topo[i] 与 topo[i+1] 存在边连通(i到i+1 或i+1到i),则定有i到i+1的边。
而如果每个topo[i] 与 topo[i+1] 都存在边连通(即有i到i+1的边)时,topo[i] 到任意topo[j]便都要边连通。
#include < iostream >
#include < stack >
#include < vector >
#define MAX 1002
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Node
{
int e, val;
} item;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
vector < vector < Node > > g(MAX);
stack < int > st;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int ord[MAX], low[MAX], id[MAX];
// ord[i]:结点i的访问次序; low[i]:与i连接的结点最先访问的次序(最高的祖先);
// id[i]:记录i结点属于第几个连通分量
int cnt, scnt, n;
// cnt记录访问次序,scnt记录强连通数; n记录结点数
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// Tarjan算法,计算强连通,邻接表形式,复杂度O(V^2)
// scnt记录强连通数,id[i]记录i结点属于第几个连通分量。
void dfs( int e)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int t, i;
int min = low[e] = ord[e] = cnt ++ ;
st.push(e);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i = 0 ; i < g[e].size(); i ++ )
{
t = g[e][i].e;
if (ord[t] == - 1 )
dfs(t);
if (low[t] < min)
min = low[t];
}
// 有回边
if (min < low[e])
{
low[e] = min;
return ;
}
// 在同一颗树(子树有回边)属于同一连通分量
do
{
id[t = st.top()] = scnt;
low[t] = n;
st.pop();
} while (t != e);
scnt ++ ;
}
void find_components( int n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int i;
memset(ord, - 1 , sizeof (ord));
cnt = 0 ;
scnt = 0 ;
for (i = 0 ; i < n; i ++ )
if (ord[i] == - 1 )
dfs(i);
}
int mat2[MAX][MAX];
int n2;
// 计算核心DAG,邻接表形式,复杂度O(V^2)
// 运行时间主要为调用求强连通分量:
// 得到scnt记录强连通数,id[i]记录i结点属于第几个连通分量。
// 返回核心DAG的结点数n2,邻接矩阵mat2[MAX][MAX]
void base_vertex()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int i, j, t;
find_components(n); // 调用求强连通分量
n2 = scnt;
for (i = 0 ; i < n2; i ++ )
for (j = 0 ; j < n2; j ++ )
mat2[i][j] = 0 ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i = 0 ; i < n; i ++ )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (j = 0 ; j < g[i].size(); j ++ )
{
t = g[i][j].e;
mat2[id[i]][id[t]] = 1 ;
}
}
}
// 拓扑排序,邻接矩阵形式,复杂度O(n^2)
// 如果无法完成排序,返回0,可以则返回1,ropo返回有序点列
// 传入图的大小n和邻接阵mat,不相邻点边权为0
int toposort2( int n, int mat[][MAX], int * topo)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int d[MAX], i, j, k;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i = 0 ; i < n; i ++ )
{ // 初始化
d[i] = 0 ;
for (j = 0 ; j < n; j ++ )
d[i] += mat[j][i]; // 入度数
}
for (k = 0 ; k < n; k ++ )
{
for (i = 0 ; d[i] && i < n; i ++ );
if (i == n) // 没有入度为0的
return 0 ;
d[i] = - 1 ; // 标记已经排序完
for (j = 0 ; j < n; j ++ ) // 删边(即减入度)
d[j] -= mat[i][j];
topo[k] = i;
}
return 1 ;
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int m, i, s, e, cas;
int topo[MAX];
scanf( " %d " , & cas);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (cas -- )
{
scanf( " %d%d " , & n, & m);
for (i = 0 ; i < n; i ++ )
g[i].clear();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i = 0 ; i < m; i ++ )
{
scanf( " %d%d " , & s, & e);
item.e = e - 1 ;
item.val = 1 ;
g[s - 1 ].push_back(item);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
base_vertex();
toposort2(n2, mat2, topo);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int flag = 1 ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i = 0 ; i < n2 - 1 ; i ++ )
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if ( ! mat2[topo[i]][topo[i + 1 ]])
{
flag = 0 ;
break ;
}
}
if (flag)
printf( " Yes\n " );
else
printf( " No\n " );
}
return 0 ;
}
posted on 2009-04-23 09:08
longshen 阅读(528)
评论(0) 编辑 收藏 引用 所属分类:
poj