P2746

Aryper · 2021-08-07 23:13:12 · 个人记录

[USACO5.3]校园网Network of Schools

POJ1236 。P2818 （没有区别，因为时间复杂度还是一样的，难道还有比线性更快的算法？？？）。

你以为它考的是 SCC ？不，其实它考的是构造。

首先要想到 SCC 缩点，这个可以根据有向图的性质和这个传递的性质想到。

那么缩点之后得到了多个简单 DAG ，既然是 DAG 就不可避免的想到了入度与出度之类的问题。

然后我们思考了一下，入度为 0 的点是不发不行的，因为其他点都到不了它。

而入度为 0 的点如果都发的话，很显然整个图上的点都能被发到，可以理解为这是个可以拓扑排序的 DAG ，然后排序的结果必然可以覆盖所有点。

所以 Subproblem A 的结果就是所有入度为 0 的点的个数 p 。

那么关于解决 Subproblem B ，其实它考的是一个构造问题。我们采用二分图的思想，把出度为 0 的点放一排（记为集合 T），入度为 0 的点放一排（记为集合 S），先不考虑独立的点。

然后的叙述并不清楚，然而我也不想画图。。。可能画图也不一定能解释清楚。。。

接下来，我们按照属于的简单 DAG 的编号来给 T 与 S 进行划分。

那么剩下我们就保证，\exists x\in S 且属于简单 DAG i ，都有它的连边末端为 y\in T 且属于简单 DAG i+1 。最后 n 号 DAG 连 1 号 DAG 即可。并且在这个过程中我们保证匹配。

这样的话我们可以顺理成章地连出了一个大环，对于剩下的点，其实随便连就可以了，但一定要保证连了。。。

那么这个图就是 SCC 了。。。因为 \forall x\in S ，我们保证它在至少一个环上了。。。这个就易证了，不作赘述。。。

既然至少在一个环上，我们就可以通过环上的某些点跳到其他环上使我们可以与所有点连通。。。

那怎么处理独立的点，我们把最后 n\rightarrow 1 的那条边像串珠子一样把这些点串起来就完了。。。

那这样的话，我们再设出度为 0 的点的个数为 q 。

Subrpoblem B 的答案大概就是 \max\{p,q\} 。

时间复杂度 O(n+m) 。

代码：

#include<iostream>
#include<cstdio>
#include<vector>
#define ll long long
using namespace std;

const ll M=2e4,N=2e2;

ll n,v,p,q,cnt,top,tot,tc,num;

ll ver[M*2+5],nxt[M*2+5],head[N+5];

ll vc[M*2+5],nc[M*2+5],hc[N+5];

ll low[N+5],dfn[N+5],stk[N+5],c[N+5];

ll deg_in[N+5],deg_out[N+5];

bool ins[N+5];

vector<ll> scc[N+5];

void add_c(ll u,ll v) {
    vc[++tc]=v;nc[tc]=hc[u];hc[u]=tc;
}

void tarjan(ll x) {
    dfn[x]=low[x]=++num;
    stk[++top]=x;ins[x]=1;
    for(ll i=head[x];i;i=nxt[i]) {
        if(!dfn[ver[i]]) {
            tarjan(ver[i]);low[x]=min(low[x],low[ver[i]]);
        }
        else {
            if(ins[ver[i]]) low[x]=min(low[x],dfn[ver[i]]);
        }
    }
    if(dfn[x]==low[x]) {
        cnt++;
        do {
            ins[stk[top]]=0;
            c[stk[top]]=cnt;
            scc[cnt].push_back(stk[top]);
        } while(x!=stk[top--]);
    }
}

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        v=read();
        while(v!=0) {
            add(i,v);v=read();
        }
    }

    for(ll i=1;i<=n;i++) {
        if(!dfn[i]) tarjan(i);
    }

    for(ll x=1;x<=n;x++) {
        for(ll i=head[x];i;i=nxt[i]) {
            if(c[x]==c[ver[i]]) continue;
            add_c(c[x],c[ver[i]]);
            deg_in[c[ver[i]]]++;
            deg_out[c[x]]++;
        }
    }

    if(cnt==1) {
        write(1);putchar('\n');
        write(0);
    }
    else {
        for(ll i=1;i<=cnt;i++) {
            if(!deg_in[i]) p++;
            if(!deg_out[i]) q++;
        }
        write(p);putchar('\n');
        write(max(p,q));
    }

    return 0;
}