HDU 2767 Proving Equivalences（强联通分量）

题意：给出n个点，m个边，问你添加多少条边，才能让这张图变成一个强联通分量图。 分析：想这个题的时候总是在想有向树和DAG的区别，貌似有点启发…我们知道，强联通分量内的点是互相可达。u能去v点，那么v点一定可以绕一大圈回去.也就每个点的入度和出度都至少是1. 按照这个性质，我们可以从点的类型切入这题。 首先进行缩点（Tarjan大法好），得到一个DAG图.然后统计每个点的入度和出度。如果某些点的入度和出度不同时大于等于1，说明它一定不在最终构造完毕的强联通图里，需要加边。 加一条边的影响是让其中的一个点出度加1，入度加1.只要让这些不符合条件的点变成符合条件即可，那么要加多少条边呢.设入度为0的点有a，出度为0,的点有b，答案是max（a,b）.因为你是加到这些点全部的入度和出度大于等于1，所以是取max 额，思考的时候还想出来了一种貌似是特例，所以是貌似嘛。如果有的点一条边都没有，就是入度出度都是0，那么它对答案的贡献也是1吗. 答案是确实，因为你缩点完了，是一个DAG，必然有两个（以上）特殊点，起点的入度必为0，终点出度一定是0，终点->（出度入度都是0的点）->起点.这样也是只用了两条边，答案是取max（a,b）.此时，入度为0的点有那个终点，还有出入都是0,出度同理，都是2.符合假想的答案。 那么实现起来就没什么困难了，先用Tarjan缩点.在得到的DAG上统计每个点的出入度。输出max(a,b)。注意，如果原图已经是一个强联通分量，那么也就不用加边了，输出0即可。

#include
using namespace std;
const int maxn = 2e4+5;
vector G[maxn];
int pre[maxn],lowlink[maxn],sccnow[maxn],dfs_clock,scc_cnt;
stack S;
void dfs(int u){
	pre[u]=lowlink[u]=++dfs_clock;
	S.push(u);
	for(int i=0;iT;
	while(T--){
		memset(in,0,sizeof(in));
		memset(out,0,sizeof(out));
		int n,m;scanf("%d%d",&n,&m);
		for(int i=0;i