1 条题解

  • 0
    @ 2021-8-8 10:44:35

    C++ :

    
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<set>
    #include<map>
    #include<functional>
    using namespace std;
    #define ll long long
     
    typedef pair<ll,int>P;
    const ll INF=1e17+10;
    const int N=105,mod=1e9+7;
    struct A{
        int to,nex;
    }edge[N*N];
    int n;
    int head[N],cnt=0,tot=0,vis[N],number;
    int dfn[N],low[N],sta[N],inx=0,fa[N];
    int in[N],out[N];
     
    void add(int from,int to){
        edge[cnt].to=to;
        edge[cnt].nex=head[from];
        head[from]=cnt++;
    }
     
    void tarjan(int x){
        dfn[x]=low[x]=++tot;
        sta[++inx]=x;
        vis[x]=1;
        for(int i=head[x];i!=-1;i=edge[i].nex){
            int v=edge[i].to;
            if(!dfn[v]){
                tarjan(v);
                low[x]=min(low[x],low[v]);
            }
            else if(vis[v]){
                low[x]=min(low[x],dfn[v]);
            }
        }
        if(low[x]==dfn[x]){
            do{
                int t=sta[inx--];
                fa[t]=number;
                vis[t]=0;
            }while(x!=sta[inx+1]);
            number++;
        }
    }
     
    void rebuild(){
        for(int i=1;i<=n;i++){
            for(int j=head[i];j!=-1;j=edge[j].nex){
                int v=edge[j].to;
                if(fa[i]!=fa[v]){
                    in[fa[v]]++;
                    out[fa[i]]++;
                }
            }
        }
    }
     
    int main(){
        int t;
        scanf("%d",&n);
        memset(head,-1,sizeof(head));
        for(int i=1;i<=n;i++){
            while(scanf("%d",&t)&&t){
                add(i,t);
            }
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]){
                tarjan(i);
            }
        }
        rebuild();
        int ru=0,chu=0;
        for(int i=0;i<number;i++){
            if(!in[i])ru++;
            if(!out[i])chu++;
        }
        if(number==1){
            printf("1\n0\n");
        }
        else{
            printf("%d\n%d\n",ru,max(ru,chu));
        }
    }
    
    • 1

    信息

    ID
    277
    时间
    1000ms
    内存
    128MiB
    难度
    9
    标签
    递交数
    8
    已通过
    7
    上传者