研究了Lynncui牛的代碼，才知道解題思路：
先Tarjan強連通縮點，（假設共n2個）得到的id[i]編號為0的分支，其出度為0（有可能是Popular Cows）。
再判斷其他強連通分支是否有出度
1）如果其中有一個分支沒有出度，則0分支不可能是Popular Cows（considered popular by every other cow）
2）如果其他所有強連通分支都有出度，
2.1）則必要其中一個分支有邊指向0分支（假設為i），
因為各連通分支之間的邊不會構成環，（反證，如果沒有邊指向0的分支，
則在n2-1個分支中都有出度，且都指向n2-1個分支中的一個）
2.2）同理可知在除i外的n2-2個分支中，定有一個分支有邊指向0分支或i分支
......
0分支為Popular Cows
#include < iostream >
#include < stack >
#include < vector >
#define MAX 10002
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, n2;
// 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 main()
{
int m, i, j, s, e, ans;
int map[MAX], flag;
while (scanf( " %d%d " , & n, & m) != EOF) {
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);
}
find_components(n);
n2 = scnt;
memset(map, 0 , sizeof (map));
ans = 0 ;
for (i = 0 ; i < n; i ++ ) {
if (id[i] == 0 ) ans ++ ;
for (j = 0 ; j < g[i].size(); j ++ ) {
e = g[i][j].e;
if (id[i] != id[e] && ! map[id[i]])
map[id[i]] = 1 ;
}
}
flag = 0 ;
for (i = 1 ; i < n2; i ++ )
if ( ! map[i]) flag ++ ;
if (flag)
cout << " 0 " << endl;
else
cout << ans << endl;
}
return 0 ;
} posted on 2009-04-23 18:17
longshen 閱讀(614)
評論(0) 編輯 收藏 引用 所屬分類:
poj