算法1
(暴力枚举) $O(n^2)$
现有$N$头牛，编号从$1$到$N$， 又有$M$对整数$(A,B)$，表示牛$A$认为牛$B$受欢迎，并且这种关系是具有传递性的。如果将这种关系抽象为牛与牛之间的有向边，那么牛$X$是认为牛$Y受欢迎就可以抽象为图中点$X$到$Y$是存在一条路径。
最终统计有多少头牛被除自己之外的所有牛认为是受欢迎的，就可以理解为牛$X$是否存在反向路径能够到达其它所有牛，如果存来，那么牛$X$符合条件，计数1次。
通过以上分析，一个简单暴力的做法就出现了：
1. 建立点之间的反向边
2. 遍历所有点，以点i为起点dfs其所有邻接点，并返回此次遍历的点的数量
3. 如果dfs(i) == n，则说明从i出发可以到达所有点，那么计数1次。
最后输出计数数量。
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010, M = 50010;
int n, m;
int h[N], e[M], ne[M], idx;
int st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int u)
{
st[u] = 1; //标记为已扩展，保证每个结点只访问一次。
int sum = 1; //从u点出发，所访问的结点总数
for(int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
if(!st[v]) sum += dfs(v);
}
return sum;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m --)
{
int a, b;
cin >> a >> b;
add(b, a);
}
int res = 0;
for(int i = 1; i <= n; i++)
{
memset(st, 0, sizeof st);
if(dfs(i) == n) res++;
}
cout << res << endl;
return 0;
}
算法2
(Tarjan算法求强连通分量 + 缩点 + 拓扑序) $O(n + m)$
相关概念
如果两个顶点可以相互通达，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。
Robert Tarjan提出的了求解有向图强连通分量的线性时间的算法，即Tarjan算法。
算法原理：
对每个点定义两个时间戳$timestamp$：
1. dfn[u]表示遍历到u的时间戳
2. low[u]表示从点u开始走，所能遍历的最小的时间戳
如果u是其所在的连通分量的最高点（时间戳最小），那么dfn[u] == low[u]。
实现步骤
- dfn[u] = low[u] = 1
- 将u点压入栈
- 遍历u所有邻接点
- 如果当前点v没有被遍历过，深度优先遍历v，求出low[v]，使用low[v]更新low[u]
- 如果当前点v被遍历过但是还在栈中（即还没有遍历完v所在的强联通分量），使用dfn[v]更新low[u]
- 遍历完u的所有连接点后，如果发现dfn[u] == low[u]，说明u是其所在的连通分量的最高点
- 将栈顶所有与u连通的点弹出，就是u所在强连通分量的点。
缩点
缩点是将每个强连通分量看作一个点，通过有向边将他们连接起来，得到一个有向无环图（DAG），也就是拓扑图。
实现步骤
- 遍历每个顶点u
- 遍历u的每个邻点v
- 如果u和v不在同一个强连通分量中，添加一条从id[u]到id[v]的有向边。
拓扑序
做完Tarjan算法后，进行缩点之后的强连通分量已经按照其编号递减的顺序完成拓扑序。
因为深度优先搜索把一个强连通分量中所有点找出之后，会给它们设置同一个编号。并且当前编号的强连通分量不会有其它还未搜索到的后继强连通分量，也就是说它的后继都已经处理完成。因为在Tarjan算法中，后继结点后入栈，所以会先被弹出栈进行处理。
既然强连通分量已完成拓扑排序，那么：
1. 如果在这个拓扑图中至少存在两个点的出度为0（终点无后继），那么就不存在被除自己之外的所有牛认为是受欢迎的牛，至少有另外一个终点没有认为它受欢迎。
2. 如果只存在一个点其出度为0，那么这个点所代表的强联通分量中的所有牛都是被除自己之外的所有牛认为是受欢迎的牛。因为在该强连通分量内部，所有点都是连通的；在该强连通分量外部，这种关系是具有传递性，最终会沿着拓扑序走到该强连通分量。
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010, M = 50010;
int n, m;
int h[N], e[M], ne[M], idx;
//dfn[i]表示结点i的时间戳
//lowe[i]表示结点i能回溯到的最早时间戳
int dfn[N], low[N], timestamp; //时间戳
//栈中当前还没有搜索完的强连通分量的所有点
int stk[N], top;
//in_stk[i]表示结点i是否在栈中
int in_stk[N];
//scc_cnt表示强连通分量的数量
int scc_cnt;
//id[i]表示结点i所在的强连通分量编号
int id[N];
//si[i]表示编号为i的强联通分量中点的数量
int si[N];
//dout[i]表示编号为i的强连通分量的出度
int dout[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++timestamp;
stk[++ top] = u, in_stk[u] = 1; //将u入栈
//遍历i的所有邻边
for(int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
//如果v点还没有遍历过
if(!dfn[v])
{
tarjan(v); //深度优先搜索v
//如果low[v]更小，则使用low[v]更新low[u]
//因为u可以到达v，所以v能回溯到时间戳，u也必然能到
low[u] = min(low[u], low[v]);
}
else //v点已经遍历过了
{
//如果v已经搜索过但还在栈中，说明v是u的后向边或者横叉边连接的点
//那么v点的时间戳一定小于u点的时间戳。
if(in_stk[v]) low[u] = min(low[u], dfn[v]);
}
}
//如果u能回溯到的最早时间戳就是自己，
//那么u必然是其所在强连通分量最早被访问的点
if(dfn[u] == low[u])
{
scc_cnt ++;
int v; // 栈中该强连通分量中的点
do
{
v = stk[top --];
in_stk[v] = 0;
id[v] = scc_cnt;
si[scc_cnt]++; //统计该强连通分量中点的数量
}while(u != v);
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m --)
{
int a, b;
cin >> a >> b;
add(a, b);
}
//处理强连通分量
for(int i = 1; i <= n; i++)
{
if(!dfn[i]) tarjan(i);
}
//遍历所有点，计算强连通分量的出度
for(int u = 1; u <= n; u++)
for(int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
//u和v不属于同一个强连通分量
if(id[u] != id[v]) dout[id[u]]++;
}
//处理所有出度为0的强连通分量，累加所有出度为0的强连通分量中的点的数量。
int sum = 0, zeros = 0;
for(int i = 1; i <= scc_cnt; i ++)
if(dout[i] == 0)
{
zeros++;
sum += si[i];
if(zeros > 1)
{
sum = 0;
break;
}
}
cout << sum << endl;
return 0;
}
顶