C++14(g++5.4) 解法, 执行用时: 972ms, 内存消耗: 28760K, 提交时间: 2019-10-07 15:51:41

#include<cstdio>
using namespace std;
int head[1000010],ne[2000010],to[2000010],cnt=0;
void add(int u,int v){
    cnt++;
    to[cnt]=v;
    ne[cnt]=head[u];
    head[u]=cnt;
}
int n,m,ans=0;
bool vis[1000010]={0};
void dfs(int r){
    vis[r]=1;
    for(int i=head[r];i!=-1;i=ne[i]){
        if(vis[to[i]]==0){
            ans++;
            dfs(to[i]);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)head[i]=-1;
    int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    dfs(1);
    printf("%d",ans);
    return 0;
}

C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 904ms, 内存消耗: 103056K, 提交时间: 2023-02-28 22:38:40

#include<cstdio>
#include<vector>

using namespace std;

const int N = 1001000;
vector<int> dad[N];
bool vis[N];

int dfs(int root)
{
    int i, u;
    vis[root] = true;
    int ret = 0;
    for(i = 0; i < dad[root].size(); i++)
    {
        u = dad[root][i];
        if(!vis[u])
            ret += dfs(u);
    }
    return ret + 1;
}
int main()
{
    int i,m,n;
    int p,q;
    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d", &p, &q);
        dad[p].push_back(q);
    }
    printf("%d\n", dfs(1)-1);
    return 0;
}

C++ 解法, 执行用时: 901ms, 内存消耗: 90416K, 提交时间: 2021-09-14 21:49:25

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n,m,ans=-1;
vector<int>e[MAXN],vis(MAXN);
void dfs(int x){
    if(vis[x])return;
    vis[x]=1;
    ans++;
    for(auto v:e[x])dfs(v);
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>m;
    for(int u,v;m--;){
        cin>>u>>v;
        e[u].push_back(v);
    }
    dfs(1);
    cout<<ans<<'\n';
    return 0;
}