企业官网建设流程全解析

济南网站建设公司哪个好点呢,微信开发者工具怎么使用,网页设计培训钱,网站科技感页面设计问题#xff1a; 本题描述了一个有向图模型#xff1a; 每个学校是一个节点 学校间的分享关系构成有向边#xff08;如果 a 分享给 b#xff0c;则存在 a→b 的边#xff09; 需要解决两个独立的问题#xff1a; 1.至少需要向几个学校发放软件#xff0c;才能让所有学校…问题本题描述了一个有向图模型每个学校是一个节点学校间的分享关系构成有向边如果 a 分享给 b则存在 a→b 的边需要解决两个独立的问题1.至少需要向几个学校发放软件才能让所有学校都获得软件相当于找到最少数量的起点使得从这些起点出发可以到达所有节点2.至少需要添加多少条边使得整个图变成强连通图使得无论从哪个学校发放软件所有学校都能获得软件思路使用 Tarjan 算法缩点后对于问题1缩点后得到 DAG有向无环图需要发放软件的学校数量 DAG 中入度为 0 的强连通分量数量因为入度为 0 的点没有其他点能到达它必须作为起点对于问题2需要使 DAG 变成强连通图最少需要添加的边数max(入度为0的点数, 出度为0的点数)特殊情况如果整个图已经是一个强连通分量答案为 0算法使用 Tarjan 算法求强连通分量对每个未访问的节点进行 DFS维护 dfn访问顺序和 low能回溯到的最早节点当 low[u] dfn[u] 时找到一个强连通分量缩点并统计度数对原图的每条边如果两端点在不同分量则在缩点后的图中添加边统计每个分量的入度和出度计算答案问题1入度为0的分量个数问题2:如果只有一个分量0否则max(入度为0的个数, 出度为0的个数)代码#includebits/stdc.husing namespace std;const int N110;int n,tot,tp,cl;vectorintg[N];int dfn[N],low[N],st[N],col[N],sz[N];int ind[N],oud[N];void tarjan(int u){dfn[u]low[u]tot;st[tp]u;for(int v:g[u]){if(!dfn[v]){tarjan(v);low[u]min(low[u],low[v]);}else if(!col[v])low[u]min(low[u],dfn[v]);}if(low[u]dfn[u]){col[u]cl;while(st[tp]!u){col[st[tp]]cl;tp--;}tp--;}}int main(){cinn;for(int i1;in;i){int x;cinx;while(x){g[i].push_back(x);cinx;}}for(int i1;in;i)if(!dfn[i])tarjan(i);for(int u1;un;u){for(int v:g[u]){if(col[u]!col[v]){ind[col[v]];oud[col[u]];}}}int ans10,ans20;for(int i1;icl;i){if(!ind[i])ans1;if(!oud[i])ans2;}coutans1endl;if(cl1)cout0;else coutmax(ans1,ans2);return 0;}