9/16腾讯研发岗笔试编程题第二题

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
#include <queue>
#define inf 0x3fffffff
using namespace std;
const int maxn=2010;
int first[maxn],sign;
int out[maxn],vis[maxn];
queue<int>q;
struct node1{
    int u,v;
}e[maxn];
struct node
{
    int to,w,next;
}edge[maxn];
void creat(){
    for(int i=0;i<maxn;i++)
        first[i]=0;
    sign=1;
}
void add_edge(int u,int v){
    edge[sign].to=v;
    edge[sign].next=first[u];
    first[u]=sign++;
}
void bfs(int s){
    q.push(s);
    while(!q.empty()){
        int top=q.front();
        q.pop();
        for(int i=first[top];i;i=edge[i].next){
            int to=edge[i].to;
            if(vis[to])continue;
            out[to]++;
            q.push(to);
        }
    }
}
void bfs1(int s){
    q.push(s);
    while(!q.empty()){
        int top=q.front();
        q.pop();
        for(int i=first[top];i;i=edge[i].next){
            int to=edge[i].to;
            if(vis[to])continue;
            out[to]--;
            q.push(to);
        }
    }
}
int main(){
    int n,m;
    int u,v;
    creat();
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d %d",&u,&v);
        e[i].u=u;
        e[i].v=v;
        if(u==v)continue;
        add_edge(u,v);
    }

    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        vis[i]=1;
        bfs(i);
    }
    creat();
    for(int i=0;i<m;i++){
        v=e[i].v;
        u=e[i].u;
        if(u==v)continue;
        add_edge(v,u);
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        vis[i]=1;
        bfs1(i);
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        if(out[i]>0)
            sum++;
    }
    printf("%d\n",sum);
    return 0;
}