思路模糊時看了DieIng大牛的思路，寫了出來...
思路：Tarjan算法計算強連通分支，然后縮點，再求其拓撲序。
（假設(shè)求得的拓撲序存儲在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]:結(jié)點i的訪問次序; low[i]:與i連接的結(jié)點最先訪問的次序(最高的祖先);
// id[i]:記錄i結(jié)點屬于第幾個連通分量
int cnt, scnt, n;
// cnt記錄訪問次序，scnt記錄強連通數(shù); n記錄結(jié)點數(shù)
// Tarjan算法，計算強連通，鄰接表形式，復(fù)雜度O(V^2)
// scnt記錄強連通數(shù)，id[i]記錄i結(jié)點屬于第幾個連通分量。
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，鄰接表形式，復(fù)雜度O(V^2)
// 運行時間主要為調(diào)用求強連通分量：
// 得到scnt記錄強連通數(shù)，id[i]記錄i結(jié)點屬于第幾個連通分量。
// 返回核心DAG的結(jié)點數(shù)n2,鄰接矩陣mat2[MAX][MAX]
void base_vertex()
{
int i, j, t;
find_components(n); // 調(diào)用求強連通分量
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 ;
}
}
}
// 拓撲排序，鄰接矩陣形式，復(fù)雜度O(n^2)
// 如果無法完成排序，返回0，可以則返回1，ropo返回有序點列
// 傳入圖的大小n和鄰接陣mat，不相鄰點邊權(quán)為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]; // 入度數(shù)
}
for (k = 0 ; k < n; k ++ ) {
for (i = 0 ; d[i] && i < n; i ++ );
if (i == n) // 沒有入度為0的
return 0 ;
d[i] = - 1 ; // 標記已經(jīng)排序完
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 閱讀(551)
評論(0) 編輯 收藏 引用 所屬分類:
poj