[Luogu] p2341 popular cattle

Title address ：

https://www.luogu.com.cn/problem/P2341

Title Description ：
Every cow dreams of being a star in the cowshed . The cow that all cows like is a star cow . All cows are narcissists , Every cow always likes its own . Between cows “ like ” It can be transmitted —— If $A$ like $B$,$B$ like $C$, that $A$ I also like $C$. It's in the bullpen $N$ A cow , Given some of the relationships between cows , Please figure out how many cows can be stars .

Input format ：
first line ： Two integers separated by spaces ：$N$ and $M$.
Next $M$ That's ok ： Two integers separated by spaces on each line ：$A$ and $B$, Express $A$ like $B$.

Output format ：
A single integer in a row , The number of star cows .

Data range ：
about $10\%$ The data of ,$N\le 20$,$M\le 50$.
about $30\%$ The data of ,$N\le 10^3$,$M\le 2\times 10^4$.
about $70\%$ The data of ,$N\le 5\times 10^3$,$M\le 5\times 10^4$.
about $100\%$ The data of ,$1\le N\le 10^4$,$1\le M\le 5\times 10^4$.

It can be used Tarjan The algorithm shrinks the graph first , In this way, we can see that the output after shrinking point is $0$ How many points of , If it's not the only one , No cow can be a star . Otherwise, the exposure is $0$ Point of size that will do . Train of thought reference https://blog.csdn.net/qq_46105170/article/details/116681582. The code is as follows ：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e4 + 10, M = 5e4 + 10;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, sz[N];
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] = true;
  for (int i = h[u]; ~i; i = ne[i]) {
    
    int v = e[i];
    if (!dfn[v]) {
    
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
  }

  if (dfn[u] == low[u]) {
    
    scc_cnt++;
    int y;
    do {
    
      y = stk[--top];
      in_stk[y] = false;
      id[y] = scc_cnt;
      sz[scc_cnt]++;
    } while (y != u);
  }
}

int main() {
    
  memset(h, -1, sizeof h);
  scanf("%d%d", &n, &m);
  while (m--) {
    
    int a, b;
    scanf("%d%d", &a, &b);
    add(a, b);
  }
  
  for (int i = 1; i <= n; i++)
    if (!dfn[i]) tarjan(i);

  for (int i = 1; i <= n; i++)
    for (int j = h[i]; ~j; j = ne[j])
      if (id[i] != id[e[j]])
        dout[id[i]]++;
  
  int zero = 0, res;
  for (int i = 1; i <= scc_cnt; i++) {
    
    if (!dout[i]) {
    
      if (++zero > 1) {
    
        res = 0;
        break;
      }
      res = sz[i];
    }
  }

  printf("%d\n", res);
}

Time complexity $O(N+M)$, Space $O(N)$.