研究了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 阅读(580)
评论(0) 编辑 收藏 引用 所属分类:
poj