poj1236专题

【算法每日一练]-图论(保姆级教程篇12 tarjan篇)#POJ3352道路建设 #POJ2553图的底部 #POJ1236校园网络 #缩点

目录          POJ3352:道路建设         思路: POJ2553:图的底部        思路: POJ1236校园网络        思路: 缩点:        思路:                   POJ3352:道路建设          由于道路要维修,维修时候来回都不能走,现要在各个景点间建设新道路以便维修时候也能保证任何

POJ1236 Network of Schools(强连通分量:Tarjan算法)

题意: 学校之间有网络系统,通过网络可以从一个学校定向的传递文件给另一个学校。现在问最少给几个学校传递文件使所有学校都能收到?最少添加几天网络边可以使整个网络连通? 要点: 就是一个基本的强连通分量,将连通分量缩成一个点,入度和出度如果都不为0说明这个点与其他点连通,所以第一问我们只要算出几个点入度为0即可,第二问我们只要算出几个点入度为0,几个点出度为0,取其中最大值即可。理解一下就是,我