lgP2746[USACO5.3]校园网

发表于 | 分类于 ， ， | 阅读数 次

链接:lgP2746[USACO5.3]校园网

题解

  • 显然分发学校向接受学校连一条边，然后缩点。
  • 子任务A显然就是入度为零的缩点个数
  • 子任务B则是入度为零和出度为零的缩点个数的最大值
  • 有一个坑点，只有一个强连通分量的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=1e5;
    struct node{
        int v,nxt;
        inline void init(int x,int y){v=x; nxt=y;}
    }e[N];
    int head[N],dfn[N],low[N],cnt,bl[N],du[N][2],n,m,in[N],stck[N],idx,tot,x,ans,res[2];
    inline void adde(int x,int y){e[cnt].init(y,head[x]);head[x]=cnt++;}
    void tarjan(int u){
        in[u]=1;
        stck[++idx]=u;
        dfn[u]=low[u]=++tot;
        for(int i=head[u],v;i!=-1;i=e[i].nxt){
            if(!dfn[v=e[i].v]){tarjan(v); low[u]=min(low[u],low[v]);}
            else if(in[v])low[u]=min(low[u],dfn[v]);
        }
        if(dfn[u]==low[u]){
            cnt++;
            do{in[stck[idx]]=0; bl[stck[idx--]]=cnt;}while(u!=stck[idx+1]);
        }
    }
    int main(){
        memset(head,-1,sizeof(head));
        scanf("%d",&n);
        rep(i,1,n)while(~scanf("%d",&x)&&x){
            adde(i,x);
        }cnt=0;
        rep(i,1,n)if(!dfn[i])tarjan(i);
        rep(u,1,n)for(int i=head[u],v;i!=-1;i=e[i].nxt)if(bl[v=e[i].v]!=bl[u]){
            du[bl[u]][0]++;
            du[bl[v]][1]++;
        }
        rep(i,1,cnt){ans+=(du[i][1]==0); res[0]+=(du[i][0]==0);res[1]+=(du[i][1]==0);}
        printf("%d\n%d",ans,cnt!=1?max(res[0],res[1]):0);
        return 0;
}