题目解析
这道题是 Tarjan 缩点 + DAG 出度分析 的经典应用。
题目解析
- 喜欢关系的传递性： 题目指出“喜欢”具有传递性。这意味着如果点 和点 处于同一个强连通分量（SCC）中，那么该分量内的所有奶牛都互相喜欢。
- 缩点的必要性： 我们可以将所有的 SCC 缩成一个点。缩点后，整个图变成了一个 DAG（有向无环图）。
- 谁能成为明星？
- 明星奶牛必须被“所有”奶牛喜欢。在缩点后的 DAG 中，这等价于：该点必须能被 DAG 中所有其他节点到达。
- 在 DAG 中，如果一个点的 出度为 0，说明它无法到达别人。
- 关键结论：如果图中只有一个出度为 0 的 SCC，那么这个 SCC 里的所有奶牛都是明星。
- 为什么？ 如果有多个出度为 0 的 SCC（假设为 和 ），那么 里的奶牛无法到达 ，反之亦然。此时没有任何一头牛能被所有人喜欢。
- 算法流程：
- 运行 Tarjan 算法求出所有 SCC。
- 统计每个 SCC 的出度。
- 统计出度为 0 的 SCC 个数。
- 如果个数为 1，答案就是该 SCC 包含的奶牛数量；否则答案为 0。
代码实现
根据你的框架完成如下：
cpp
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* date: 2025-12-29 10:52:38
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e6+5;
const int maxe = 4e6+5;
const int mod = 1e9+7;
int n, m;
struct linkList {
typedef struct {int u,v,w,next;} edge;
edge e[maxe];
int h[maxn], edge_cnt = 0;
linkList(){
reset();
}
void reset() {
edge_cnt = 0;
memset(h, -1, sizeof(h));
}
void add(int u,int v,int w=0){
e[edge_cnt] = {u,v,w,h[u]};
h[u] = edge_cnt++;
}
int operator()(int u){ return h[u]; }
edge& operator[](int i){ return e[i]; }
} e;
struct TarjanScc {
int n, timer;
std::stack<int> st;
bool in_stack[maxn];
int dfn[maxn], low[maxn], scc_id[maxn];
int scc_cnt;
int sz[maxn]; // 新增：记录每个 SCC 包含的节点数量
void set(int _n) {
n = _n;
timer = scc_cnt = 0;
memset(dfn, 0, sizeof(dfn));
memset(in_stack, 0, sizeof(in_stack));
memset(sz, 0, sizeof(sz));
}
void dfs(int u) {
dfn[u] = low[u] = ++timer;
st.push(u);
in_stack[u] = true;
for (int i = e(u); ~i ; i = e[i].next) {
int v = e[i].v;
if (!dfn[v]) {
dfs(v);
low[u] = std::min(low[u], low[v]);
} else if (in_stack[v]) {
low[u] = std::min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
scc_cnt++;
while (1) {
int v = st.top(); st.pop();
in_stack[v] = 0;
scc_id[v] = scc_cnt;
sz[scc_cnt]++; // 累加该 SCC 的大小
if (v == u) break;
}
}
}
void solve() {
for (int i = 1; i <= n; i++) {
if (!dfn[i]) dfs(i);
}
}
} tscc;
int out_degree[maxn]; // 记录每个 SCC 的出度
signed main () {
ios::sync_with_stdio(false); cin.tie(0);
if(!(cin >> n >> m)) return 0;
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
e.add(u, v);
}
tscc.set(n);
tscc.solve();
// 遍历所有原图的边，统计 SCC 的出度
for(int i = 0; i < e.edge_cnt; i++) {
int u = e.e[i].u;
int v = e.e[i].v;
// 如果边连接了两个不同的 SCC
if(tscc.scc_id[u] != tscc.scc_id[v]) {
out_degree[tscc.scc_id[u]]++;
}
}
int zero_out_cnt = 0; // 出度为 0 的 SCC 数量
int star_scc_idx = 0; // 记录出度为 0 的 SCC 编号
for(int i = 1; i <= tscc.scc_cnt; i++) {
if(out_degree[i] == 0) {
zero_out_cnt++;
star_scc_idx = i;
}
}
// 判定：如果有且仅有一个出度为 0 的 SCC
if(zero_out_cnt == 1) {
cout << tscc.sz[star_scc_idx] << endl;
} else {
// 如果有多个出度为 0 的 SCC，或者没有点（n=0），则没有明星
cout << 0 << endl;
}
return 0;
}
关键细节说明
tscc.sz数组：我在TarjanScc结构体中添加了一个sz数组，用来在弹出栈时直接统计该强连通分量里有多少头奶牛。- 出度判定：明星奶牛在 DAG 的“末端”，所以它们所在分量的出度必须为 0。如果有多于一个分量出度为 0，它们之间无法互通，就不存在能被“所有人”喜欢的奶牛。