给定一个有向图，问最少增加多少条边后变成强连通图
tarjan求求强连通分量并缩点，如果强连通分量个数为1，则需要边数为0，
否则为缩点后点入度和出度的最大值，
证明：当入度或者出度不为0时，则可以通过传递性使其相同，所以只需要考虑入度或者出度为0的点
即可。因为要求增加尽量少的边，所以将入度和出度都为0的点相连，边的方向为出度为0的指向入度为0的顶点。
当入度为0或者出度为0的点有剩余时，则任意取一个点进行连边。
所以当有向图为强连通图时答案为0，否则最小值为入度和入度的最大值
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 20005;
const int maxm = 100005;
struct node{
int v,next;
}edge[maxm];
int head[maxn],low[maxn],dfn[maxn],sta[maxn],in[maxn],out[maxn],belong[maxn],vis[maxm];
int Time,id,top,num,total;
void add_edge(int u,int v){
edge[id].v = v;edge[id].next = head[u];head[u] = id++;
}
void tarjan(int u){
low[u] = dfn[u] = ++Time;
sta[top++] = u;in[u] = 1;
for(int id = head[u]; id != -1; id = edge[id].next){
int v = edge[id].v;
if(!dfn[v]){
tarjan(v);
if( low[u] < low[v])total++;
low[u] = min(low[u],low[v]);
}
else if( in[v] )low[u] = min(low[u],low[v]);
}
if( low[u] == dfn[u]){
num ++;
do{
int t = sta[--top];
in[t] = 0;
belong[t] = num;
}while( sta[top] != u);
}
}
int main(){ int t;
int n,m;
int u,v;
int cnt;
scanf("%d",&t);
while( t-- ){
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head)),id = 0;
while( m-- ){
scanf("%d%d",&u,&v);
add_edge(u,v);
}
memset(dfn,0,sizeof(dfn));
Time = num = total = cnt = 0;
for(int i = 1; i <= n;i++){
if(!dfn[i])
tarjan(i);
}
if( num == 1){puts("0");continue;}
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(int u = 1; u <= n; u++){
for(int id = head[u]; id != -1; id = edge[id].next){
int v = edge[id].v;
if( belong[u] != belong[v]){
in[belong[v]]++;out[belong[u]]++;
}
}
}
int indeg = 0,outdeg = 0;
for(int i = 1; i <= num; i++){
if( !in[i])indeg ++;
if( !out[i])outdeg++;
}
printf("%d\n",indeg > outdeg ? indeg : outdeg);
}
return 0;
}