题目链接：http://poj.org/problem?id=2186
题目意思大概是：给定N（N<=10000)个点和M（M<=50000)条有向边，求有多少个“受欢迎的点”。所谓的“受欢迎的点”当且仅当任何一个点出发都能到达它。
原来的图是无序且可能有环，用tarjan缩点，变成一个DAG。受欢迎点的出度一定为0，所以缩点后求有多少个连通分量的出度是0，要是大于1则没有受欢迎的点，等于1的话求出这个出度为0的连通分量有多少个点。
强联通分量tarjan算法里邻接表用vector一般好理解，但是速度不及链式前向星，链式前向星学习链接：http://blog.csdn.net/acdreamers/article/details/16902023
AC代码如下：
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std;
const int MAXN = 1e4 + ;
struct data {
int next , to;
}edge[MAXN * ];
int head[MAXN] , low[MAXN] , dfn[MAXN] , block[MAXN] , st[MAXN];
int top , ord , sccnum;
bool instack[MAXN] , out[MAXN]; void init(int n) {
for(int i = ; i <= n ; i++) {
low[i] = dfn[i] = ;
head[i] = -;
instack[i] = false;
}
top = ord = sccnum = ;
} void tarjan(int u) {
low[u] = dfn[u] = ++ord;
st[++top] = u;
instack[u] = true;
for(int i = head[u] ; ~i ; i = edge[i].next) { //链式前向星
int v = edge[i].to;
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u] , low[v]);
}
else if(instack[v]) {
low[u] = min(low[u] , dfn[v]);
}
}
if(low[u] == dfn[u]) {
int v;
sccnum++;
do {
v = st[top--];
instack[v] = false;
block[v] = sccnum;
}while(u != v);
}
} int main()
{
int n , m , u , v;
while(~scanf("%d %d" , &n , &m)) {
init(n);
for(int i = ; i < m ; i++) {
scanf("%d %d" , &u , &v);
edge[i].to = v; //链式前向星
edge[i].next = head[u];
head[u] = i;
}
for(int i = ; i <= n ; i++) {
if(!dfn[i])
tarjan(i);
}
memset(out , false , sizeof(out)); //缩点是否有入度
for(int u = ; u <= n ; u++) {
for(int i = head[u] ; ~i ; i = edge[i].next) { //链式前向星
int v = edge[i].to;
if(block[v] != block[u]) //不是同一个连通分量
out[block[u]] = true;
}
}
int res = , op = -;
for(int i = ; i <= sccnum ; i++) {
if(!out[i]) { //出度为0的点
res++;
op = i;
}
}
if(res > ) {
printf("0\n");
}
else {
res = ;
for(int i = ; i <= n ; i++) {
if(block[i] == op)
res++;
}
printf("%d\n" , res);
}
}
}