最受欢迎的牛

tarjan强连通分量 T3 模板题 P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自

恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 A 喜欢 B，B 喜欢 C，那么 A 也喜欢 C。牛栏里共有 N 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

第一行：两个用空格分开的整数：N 和 M。

接下来 M 行：每行两个用空格分开的整数：A 和 B，表示 A 喜欢 B。

input

3 3
1 2
2 1
2 3

output

1

思路

如果是暴力做法, 对于每一个点, 遍历其他所有点, 是否满足都对该点有一条边, 来判断。时间复杂度很高。

可以用 tarjan 缩点成为一个拓扑图： a->b->c->d->e 显然需要关心最后一个节点, 该点没有子节点, 那么对于它来说, 前面所有点都能到达该点, 该点就是最受欢迎的。 但如果 还有一条边为 d->f 即有两个出度为0的点, 那么就不存在最受欢迎的点。

总思路是：tarjan求强连通分量并缩点成为拓扑图, 同时计算出度, 遍历所有强连通分量根节点, 找出度为0的点数量, 若为1则加上该强连通分量的点数量, 若大于1则输出0。

代码

const int N = 1e5 + 10;
 
int h[N], e[N], ne[N], idx;
int dfs[N], low[N];
int stk[N], top;
int id[N], timestamp, scc_cnt;
int dout[N], scc_size[N];
bool in_stk[N];
int n, m;
 
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
 
void tarjan(int u)
{
    dfs[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
 
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfs[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j])
            low[u] = min(low[u], dfs[j]);
    }
 
    if (low[u] == dfs[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            scc_size[scc_cnt]++;
 
        } while (y != u);
    }
}
 
int main()
{
    FasterIO;
    mem(h, -1);
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
 
    for (int i = 1; i <= n; i++)
        if (!dfs[i])
            tarjan(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])
        {
            zeros++;
            sum += scc_size[i];
            if (zeros > 1)
            {
                sum = 0;
                break;
            }
        }
    cout << sum << endl;
    return 0;
}