E_皇城PK

可以当成一道强连通分量缩点的板子,每次连一条从b向a的有向边

跑一遍tarjan,记录缩点后的点的数量以及出度

出度为0且连通分量中点的数量为1的点的数量即为答案

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int h[N],e[N],ne[N],idx;
int dfn[N],low[N],id[N],dout[N],timestamp;
int stk[N],top,scc_cnt, s[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){
    dfn[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(!dfn[j]){
            low[u] = min(low[u],low[j]);
        }else if(in_stk[j])low[u] = min(low[u],dfn[j]);
    }

    if(low[u] == dfn[u]){
        scc_cnt++;
        int y;
        do{
            y = stk[top--];
            in_stk[y] = false;
            s[scc_cnt]++;
            id[y] = scc_cnt;
        }while(y!=u);
    }
}
int main()
{
    scanf("%d%d", &n, &m);

    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d", &a, &b);
        add(b,a);
    }

    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]){
            int k = e[j];
            int a = id[i], b = id[k];
            if(a!=b){
                dout[a] ++;
            }
        }
    }

    int ans = 0;
    for(int i = scc_cnt;i;i--)
        if(!dout[i]&&s[i]==1)ans++;

    printf("%d",ans);
}