C++14 解法, 执行用时: 6ms, 内存消耗: 632KB, 提交时间: 2020-09-13

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int main(){
    int n,m,u,v,cnt;
    while(cin>>n>>m){
        vector<vector<int>>g(n+1,vector<int>());
        vector<vector<bool>>vis(n+1,vector<bool>(n+1,false));
        for(int i=0;i<m;++i){
            cin>>u>>v;
            g[u].push_back(v);
        }
        vector<int>in(n+1),out(n+1);
        queue<int>q;
        for(int i=1;i<=n;++i){
            q.push(i);
            vis[i][i]=true;
            while(q.size()){
                int u=q.front();
                q.pop();
                for(int &v:g[u]){
                    if(!vis[i][v]){
                        vis[i][v]=true;
                        out[i]++;
                        in[v]++;
                        q.push(v);
                    }
                }
            }
        }
        cnt=0;
        for(int i=1;i<=n;++i){
            cnt+=(in[i]>out[i]);
        }
        cout<<cnt<<endl;
    }
}

C++14 解法, 执行用时: 6ms, 内存消耗: 1400KB, 提交时间: 2020-09-10

#include <bits/stdc++.h>
using namespace std;

vector<int> G[1001];
bool C[1001][1001] = {false};
int main(){
    int n, m, u, v, cnt=0;
    scanf("%d%d", &n, &m);
    for(int i=0;i<m;i++){
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    int S[n+1]={0}, T[n+1]={0};
    // memset(S, 0, sizeof(S));
    // memset(T, 0, sizeof(T));
    queue<int> q;
    for(int i=1;i<=n;i++){
        q.push(i);
        C[i][i] = true;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(auto &v: G[u]){
                if(!C[i][v]){
                    C[i][v] = true;
                    S[i]++;
                    T[v]++;
                    q.push(v);
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        if(T[i] > S[i])
            cnt++;
    printf("%d\n", cnt);
    return 0;
}