367. 学校网络(Tarjan强连通分量)[通俗易懂]

全栈程序员站长

发布于 2022-09-22 15:19:35

39500

代码可运行

文章被收录于专栏：全栈程序员必看全栈程序员必看

运行总次数：0

代码可运行

一些学校连接在一个计算机网络上，学校之间存在软件支援协议，每个学校都有它应支援的学校名单（学校 A 支援学校 B，并不表示学校 B 一定要支援学校 A）。

当某校获得一个新软件时，无论是直接获得还是通过网络获得，该校都应立即将这个软件通过网络传送给它应支援的学校。

因此，一个新软件若想让所有学校都能使用，只需将其提供给一些学校即可。

现在请问最少需要将一个新软件直接提供给多少个学校，才能使软件能够通过网络被传送到所有学校？

最少需要添加几条新的支援关系，使得将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件？

输入格式第 1 行包含整数 N，表示学校数量。

第 2…N+1 行，每行包含一个或多个整数，第 i+1 行表示学校 i 应该支援的学校名单，每行最后都有一个 0 表示名单结束（只有一个 0 即表示该学校没有需要支援的学校）。

输出格式输出两个问题的结果，每个结果占一行。

数据范围 2≤N≤100

输入样例：
5
2 4 3 0
4 5 0
0
0
1 0
输出样例：
1
2

题解 Tarjan算法求强连通分量。对每个强连通分量缩点，然后整个图是一个拓扑图

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
const int M = N * N;
struct Edge{ 
   
    int v,next;
}edge[M];
int head[N],cnt;
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
int num[N],low[N],dfn;
int scc[N],sccno;
int sta[N],top,in_sta[N];
int in[N],out[N];
int n,m;
void Tarjan(int u){ 
   
    low[u] = num[u] = ++ dfn;
    sta[top ++] = u,in_sta[u] = true;
    for(int i = head[u];~i;i = edge[i].next){ 
   
        int v = edge[i].v;
        if(!num[v]){ 
   
            Tarjan(v);
            low[u] = min(low[v],low[u]);
        }else if(in_sta[v]){ 
   
            low[u] = min(low[u],num[v]);
        }
    }
    if(num[u] == low[u]){ 
   
        sccno ++;
        while(1){ 
   
            int t = sta[-- top];
            in_sta[t] = false;
            scc[t] = sccno;
            if(t == u)break;
        }
    }
}
int main(){ 
   
    memset(head,-1,sizeof head);
    cin>>n;
    int x;
    for(int i = 0;i < n;i ++){ 
   
        while(cin>>x,x){ 
   
            add(i + 1,x);
        }
    }
    for(int i = 1;i <= n;i ++){ 
   
        if(!num[i])Tarjan(i);
    }
    for(int i = 1;i <= n;i ++){ 
   
        for(int j = head[i];~j;j = edge[j].next){ 
   
            int v = edge[j].v;
            int a = scc[i],b = scc[v];
            if(a != b){ 
   
                in[b] ++,out[a] ++;
            }
        }
    }
    int c_in = 0,c_out = 0;
    for(int i = 1;i <= sccno;i ++){ 
   
        if(!in[i])c_in ++;
        if(!out[i])c_out ++;
    }
    cout<<c_in<<endl;
    if(sccno == 1)cout<<0<<endl;
    else cout<<max(c_in,c_out)<<endl;
    return 0;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168618.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

java