算法1
Floyd算法求闭包
本质上将Floyd算法中更新距离的方式改为了if (dist[i][k] && dist[k][j]) dist[i][j] = 1;可以从动态规划的角度去理解这样的更新方式,其中此时的dist[i][k]以及dist[k][j]表示只经过{1,2,..,k}这个集合中的点,从i到k的最小距离是多少。那么此时如果i能到k且k能到j,那么dist[i][j]就不是并不是正无穷,应当被更新为1。
这样写代码以及思考相对容易,但其冗长的复杂度在现在的数据范围内是不足以AC的。具体的实现与343.排序几乎是一样的
时间复杂度
这样的Floyd算法复杂度为O(n^3)
算法2
Tarjan缩点算法
使用Tarjan算法先找到原图中的所有强连通块(strongly connected components),随后我们将强连通块看作一个整体,缩成一个点。此时原图被等效变换成一个拓扑图,那么题目中想要找到的牛的数量也就是出度为0的连通块中的点的数量。(注意如果有>=2个这样的连通块,那么就不存在这样的受欢迎的牛,特判一下即可)
时间复杂度
Tarjan算法的时间复杂度是O(n+m),算法的其他步骤中算连通块出度的复杂度为O(n),找到出度为0的连通块的复杂度为O(n),因此总时间复杂度就是O(n+m)。
C++ 代码
# include <iostream>
# include <cstring>
# include <algorithm>
using namespace std;
const int N = 1e4 + 10, M = 5e4 + 10;
int h[N], e[M], ne[M], idx;
int stk[N], top;
int dfn[N], low[N], dout[N], s[N], id[N];
bool in_stack[N];
int n, m, scc_cnt, time_stamp;
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int ver){
dfn[ver] = low[ver] = ++time_stamp;
stk[++top] = ver, in_stack[ver] = true;
for (int i = h[ver]; ~i; i = ne[i]){
int j = e[i];
if (!dfn[j]){
dfs(j);
low[ver] = min(low[ver], low[j]);
}
else if (in_stack[ver]) low[ver] = min(low[ver], dfn[j]);
}
if (dfn[ver] == low[ver]){
++scc_cnt;
int y;
do{
y = stk[top--];
id[y] = scc_cnt;
s[scc_cnt] ++;
}while (y != ver);
}
}
int main(){
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m--){
int a, b;
scanf("%d%d", &a, &b);
add(a,b);
}
for (int i = 1; i <=n; i++)
if (!dfn[i]) dfs(i); // 可能原图是不连通的
// 将图进行缩点
for (int i = 1; i <= n; i++){
for (int j = h[i]; ~j; j = ne[j]){
int k = e[j];
int a = id[i], b = id[k];
if (a != b) dout[a]++;
}
}
int zeros = 0, sum = 0;
for (int i = 1; i <= scc_cnt; i++){
if (!dout[i]){
sum += s[i];
zeros++;
}
if (zeros > 1){
sum = 0;
break;
}
}
printf("%d\n", sum);
return 0;
}