计蒜客商业信息共享（tarjan，加最少的边构成强联通图）

题目链接&＃xff1a;

计蒜客商业信息共享

题目大意&＃xff1a;

1.用最少的公司&＃xff0c;将所有的信息传递给其他的公司。

2.最少加多少条边&＃xff0c;使图变成强联通图。

题目思路&＃xff1a;

第一个问题&＃xff1a;只要统计出新图中入度为0的点即可。

第二个问题&＃xff1a;不难发现&＃xff0c;在有向无环图中&＃xff0c;要实现对于任意点都可到达其他剩余点&＃xff0c;需要添加边的数量 &＃61; $max($入度为 0 点的个数&＃xff0c;出度为 0 点的个数$)$。

注意的点&＃xff1a;

在计算第二个问题的时候&＃xff0c;要考虑此图为强联通图的情况&＃xff01;&＃xff01;&＃xff01;如果为强联通图直接输出0&＃xff01;&＃xff01;&＃xff01;

代码&＃xff1a;

#include
using namespace std;
const int maxn&＃61;2e5&＃43;10;
vectorv[maxn];//邻接表,存原图
vectorscc[maxn];//缩点后的图
stacks;
int dfn[maxn],low[maxn],tot,ins[maxn];
//dfn是否为0可以判断点是否访问过&＃xff0c;ins数组用来判断点是否在栈中
//dfn数组表示顶点dfs的时间戳&＃xff0c;low[]为u能够追溯到的最早的栈中顶点的次序号
int scc_cnt;//强联通分量的个数
int sccnum[maxn];//缩点数组&＃xff0c;表示某个点对应的缩点值
int in[maxn],out[maxn];//出度入度int n,m;
void readin()
{int x,y;tot&＃61;0;scc_cnt&＃61;0;fill(ins,ins&＃43;maxn,0);fill(sccnum,sccnum&＃43;maxn,0);fill(in,in&＃43;maxn,0);fill(out,out&＃43;maxn,0);scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) v[i].clear();for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){while(scanf("%d",&x)){if(x&＃61;&＃61;0) break;v[i].push_back(x);}}
}
void tarjan(int x)
{low[x]&＃61;dfn[x]&＃61;&＃43;&＃43;tot;//s.push(x);ins[x]&＃61;1;for(int i&＃61;0;i}int main()
{readin();for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(!dfn[i]){tarjan(i);}}//出度入度的统计方法for(int u&＃61;1;u<&＃61;n;u&＃43;&＃43;){for(int i&＃61;0;i}