思路模糊时看了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;
struct Node 
{
int e, val;
} item;
vector < vector < Node > > g(MAX);
stack < int > st;
int ord[MAX], low[MAX], id[MAX];
// ord[i]:结点i的访问次序; low[i]:与i连接的结点最先访问的次序(最高的祖先);
// id[i]:记录i结点属于第几个连通分量
int cnt, scnt, n;
// cnt记录访问次序，scnt记录强连通数; n记录结点数
// Tarjan算法，计算强连通，邻接表形式，复杂度O(V^2)
// scnt记录强连通数，id[i]记录i结点属于第几个连通分量。
void dfs( int e)
{
int t, i;
int min = low[e] = ord[e] = cnt ++ ;
st.push(e);
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)
{
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()
{
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 ;
for (i = 0 ; i < n; i ++ ) {
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)
{
int d[MAX], i, j, k;
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()
{
int m, i, s, e, cas;
int topo[MAX];
scanf( " %d " , & cas);
while (cas -- ) {
scanf( " %d%d " , & n, & m);
for (i = 0 ; i < n; i ++ )
g[i].clear();
for (i = 0 ; i < m; i ++ ) {
scanf( " %d%d " , & s, & e);
item.e = e - 1 ;
item.val = 1 ;
g[s - 1 ].push_back(item);
}
base_vertex();
toposort2(n2, mat2, topo);
int flag = 1 ;
for (i = 0 ; i < n2 - 1 ; i ++ ) {
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 阅读(530)
评论(0) 编辑 收藏 引用 所属分类:
poj