题目背景
本题测试数据已修复。
题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 AA 喜欢 BB，BB 喜欢 CC，那么 AA 也喜欢 CC。牛栏里共有 NN 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。
输入格式
第一行：两个用空格分开的整数：NN 和 MM。
接下来 MM 行：每行两个用空格分开的整数：AA 和 BB，表示 AA 喜欢 BB。
输出格式
一行单独一个整数，表示明星奶牛的数量。
输入输出样例
输入 #1复制
3 3 1 2 2 1 2 3
输出 #1复制
1
说明/提示
只有 3 号奶牛可以做明星。
【数据范围】
对于 10% 的数据，N≤20，M≤50。
对于 30% 的数据，N≤103，M≤2×104。
对于 70% 的数据，N≤5×103，M≤5×104。
对于100% 的数据，1≤N≤104，41≤M≤5×104。
强连通分量的板子题。
把同一强连通分量中的点缩为一个点，找到出度为0的强连通分量，该强连通分量中的所有点都是被所有牛喜欢的，都是最受欢迎的牛，如果有多个出度为0的强连通分量，说明原图不连通，没有任何一头牛被所有牛喜欢。
Kosaraju 算法，复杂度 O(N+M) ，视频讲解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e4 + 10;
const int M = 5e4 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;struct Edge {int to, next;
}edge1[M], edge2[M]; ///原图和逆图
int head1[N], head2[N];
bool mark1[N], mark2[N];
int tot1, tot2;
int cnt1, cnt2;
int st[N]; ///时间戳
int belong[N];
int num; ///中间变量，用来数某个连通分量中点的个数
int setnum[N];///强连通分量中点的个数，编号 0?cnt2-1
int n, m;void addedge(int u, int v) {edge1[tot1].to = v;edge1[tot1].next = head1[u];head1[u] = tot1++;edge2[tot2].to = u;edge2[tot2].next = head2[v];head2[v] = tot2++;
}void dfs1(int u) {mark1[u] = 1;for(int i = head1[u]; ~i; i = edge1[i].next)if(!mark1[edge1[i].to])dfs1(edge1[i].to);st[cnt1++] = u;}void dfs2(int u) {mark2[u] = 1;num++;belong[u] = cnt2;for(int i = head2[u]; ~i; i = edge2[i].next)if(!mark2[edge2[i].to])dfs2(edge2[i].to);
}void solve(int n) {memset(mark1, 0, sizeof(mark1));memset(mark2, 0, sizeof(mark2));cnt1 = cnt2 = 0;for(int i = 1; i <= n; ++i) ///dfs原图求时间戳if(!mark1[i])dfs1(i);for(int i = cnt1 - 1; i >= 0; --i) { ///dfs逆图if(!mark2[st[i]]) {num = 0;dfs2(st[i]);setnum[cnt2++] = num;}}
}
int deg[N];void init() {tot1 = tot2 = 0;memset(head1, -1, sizeof(head1));memset(head2, -1, sizeof(head2));memset(deg, 0, sizeof(deg));
}int main() {init();int u, v;scanf("%d%d", &n, &m);for(int i = 1; i <= m; ++i) {scanf("%d%d", &u, &v);addedge(u, v);}solve(n);///缩点 同一强连通分量的点缩为1个点，下标就是强连通分量的标号for(int i = 1; i <= n; ++i) {for(int j = head2[i]; ~j; j = edge2[j].next) {if(belong[i] != belong[edge2[j].to])deg[belong[edge2[j].to]]++; ///edge2是逆图，入点的出度++}}int ans = 0;for(int i = 0; i < cnt2; ++i) { ///cnt2是强连通分量的个数if(deg[i] == 0) { ///找到出度为0的点if(ans) { ///如果缩点后图中有 > 1个出度为0的点，说明原图不连通，没有一头牛被所有牛喜欢printf("0\n");return 0;}ans = setnum[i]; ///该强连通分量中的牛都被所有牛喜欢}}printf("%d\n", ans);return 0;
}Tarjan 算法，复杂度 O(N+M) ，视频讲解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e4 + 10;
const int M = 5e4 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;struct Edge {int to, next;
}edge[M];int head[N], tot, n, m;
int low[N], dfn[N], stk[N], belong[N];///dfn时间戳 stk栈 belong属于哪个强连通分量
int tim, top, scc; ///tim时间戳 scc强连通分量个数
bool instack[N]; ///标记是否已在栈中
int num[N]; ///每个强连通分量大小void addedge(int u, int v) {edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;
}void Tarjin(int u) {int v;low[u] = dfn[u] = ++tim;stk[top++] = u;instack[u] = 1;for(int i = head[u]; ~i; i = edge[i].next) {v = edge[i].to;if(!dfn[v]) {Tarjin(v);if(low[u] > low[v]) low[u] = low[v]; ///发现回路 更新}else if(instack[v] && low[u] > dfn[v])low[u] = dfn[v];}if(low[u] == dfn[u]) { ///发现一个强连通分量scc++;do {v = stk[--top];instack[v] = 0;belong[v] = scc;num[scc]++;}while(v != u); ///回溯}
}void solve(int n) {memset(dfn, 0, sizeof(dfn));memset(instack, 0, sizeof(instack));memset(num, 0, sizeof(num));tim = scc = top = 0;for(int i = 1; i <= n; ++i)if(!dfn[i])Tarjin(i);
}void init() {tot = 0;memset(head, -1, sizeof(head));
}int du[N];int main() {init();int u, v;scanf("%d%d", &n, &m);for(int i = 1; i <= m; ++i) {scanf("%d%d", &u, &v);addedge(u, v);}solve(n);for(int i = 1; i <= n; ++i) {for(int j = head[i]; ~j; j = edge[j].next) {if(belong[i] != belong[edge[j].to]) {du[belong[i]]++;}}}int ans = 0;for(int i = 1; i <= scc; ++i) {if(du[i] == 0) {if(ans) {printf("0\n");return 0;}ans = num[i];}}printf("%d\n", ans);return 0;
}