Network of Schools

Description

Input

Output

Sample Input

5
2 4 3 0
4 5 0
0
0
1 0

Sample Output

1
2

Source

N(2<N<100)各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输，问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。2，至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。

题解

参照嘉庆帝的题解。

我们可以先tarjan求出scc，进行缩点求出dag图，然后我们考虑第一个问题，求最少发几套软件可以全覆盖，首先题意已经保证了是联通的。然后我们可以想，如果我们把所有没有入边的点都放上软件，是一定可行的。有入边的一定会通过一些边最终从一定有出边的发放软件的地方获得软件。

然后我们考虑第二个问题。这是一个连通图。如果我们有些点没有入点，有些点没出点。那我们如果想办法将入点和一些出点相连，就能保证最后会成为很多圆相连。这样子答案就是没有入边的点和没有出边的点的最大值。意思就是说把这些点连成一个环。

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

#include<iostream>
#include<vector>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
    for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=101;
int n,dfn[N],low[N],num=0;
int st[N],top=0,tot=0,c[N],ru[N],chu[N];
bool v[N];
vector<int> e[N],scc[N],sc[N];

void tarjan(int x){
    dfn[x]=low[x]=++num;
    st[++top]=x;
    v[x]=1;
    for(unsigned i=0;i<e[x].size();++i){
        int y=e[x][i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(v[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        v[x]=0;
        scc[++tot].push_back(x);
        c[x]=tot;
        int y;
        while(x!=(y=st[top--])){
            scc[tot].push_back(y);
            v[y]=0;
            c[y]=tot;
        }
    }
}
int main(){
    read(n);
    for(int i=1;i<=n;++i){
        for(int x;read(x);) e[i].push_back(x);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i]) tarjan(i);
    for(int x=1;x<=n;++x)
        for(unsigned i=0;i<e[x].size();++i){
            int y=e[x][i];
            if(c[x]==c[y]) continue;
            sc[c[x]].push_back(c[y]);
            ++ru[c[y]];
            ++chu[c[x]];
        }
    int ansa=0,ansb=0;
    for(int i=1;i<=tot;++i){
        if(!ru[i]) ++ansa;
        if(!chu[i]) ++ansb;
    }
    printf("%d\n",ansa);
    if(tot==1) puts("0");
    else printf("%d\n",max(ansa,ansb));
    return 0;
}

POJ1236 Network of Schools

原文：https://www.cnblogs.com/autoint/p/10959821.html