1 条题解

  • 1
    @ 2025-10-5 15:21:15
    #include<bits/stdc++.h>
    using namespace std;
    void read(int &h){
        char o;
        int x=0,y=1;
        o=getchar_unlocked();
        while(!(o<='9'&&o>='0')){
            if(o=='-'){
                y=-1;
            }
            o=getchar_unlocked();
        }
        while(o<='9'&&o>='0'){
            x*=10;
            x+=o-'0';
            o=getchar_unlocked();
        }
        h=x*y;
        return ;
    }
    const int N=2e5+10;
    int n,m,dp[N],ind[N],u,v,cnt;
    vector<int> g[N];
    queue<int> q;
    int main(){
        ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
        read(n);read(m);
        for(int i=1;i<=m;i++){
            read(u);read(v);
            ind[v]++;
            g[u].push_back(v);
        }
        for(int i=1;i<=n;i++){
            if(!ind[i]&&g[i].size()){
                q.push(i);
                dp[i]=1;
            }
        }
        while(!q.empty()){
            int now=q.front();
            q.pop();
            if(!g[now].size()){
                cnt+=dp[now];
            }
            for(int it:g[now]){
                dp[it]+=dp[now];
                ind[it]--;
                if(!ind[it]){
                    q.push(it);
                }
            }
        }
        cout<<cnt;
        return 0;
    }
    
    
    • 1

    信息

    ID
    7213
    时间
    1000ms
    内存
    125MiB
    难度
    5
    标签
    递交数
    7
    已通过
    5
    上传者