题意：
给你一张有向图，问你最少加多少条边这张图强连通
思路：
缩点之后，如果不为1个点，答案为出度为0与入度为0的点的数量的最大值
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
//#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<unordered_map> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 5e4+;
const int maxm = 2e6+;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0); vector<int>g[maxn];
int f[maxn];
int color[maxn],dfn[maxn],low[maxn],stack[maxn],vis[maxn],cnt[maxn];
int in[maxn],out[maxn];
int top,n,m,sum,ans;
int deep = ;
void tarjan(int u){
dfn[u]=++deep;
low[u]=deep;
vis[u]=;
stack[++top]=u;
int sz=g[u].size();
for(int i=;i<sz;i++){
int v=g[u][i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else{
if(vis[v]){
low[u]=min(low[u],low[v]);
}
}
}
if(dfn[u]==low[u]){
color[u]=++sum;
vis[u]=;
while(stack[top]!=u){
color[stack[top]]=sum;
vis[stack[top--]]=;
}
top--;
}
return;
}
PI edge[maxn];
vector<int>v[maxn];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void dfs(int x, int fa){
if(x!=fa){
int t1 = find(x);
int t2 = find(fa);
f[t1]=t2;
}
if(v[x].size()==&&x!=fa&&vis[x]==){vis[x]=;ans++;}
for(int i = ; i <(int)v[x].size(); i++){
int y = v[x][i];
dfs(y,fa);
}
}
int main() {
while(~scanf("%d %d", &n, &m)){
deep=;
top=ans=sum=;
for(int i = ; i <= n; i++){
f[i]=i;
color[i]=low[i]=dfn[i]=stack[i]=vis[i]=cnt[i]=;
g[i].clear();
v[i].clear();in[i]=out[i]=;
}
for(int i = ; i <= m; i++){
int x,y;
scanf("%d %d", &x, &y);
edge[i] = make_pair(x,y);
g[x].pb(y);
}
for(int i = ; i <= n; i++){
if(!dfn[i])tarjan(i);
}
/*for(int i = 1; i <= n; i++){
printf("--%d %d %d\n",i,color[i],low[i]);
}*/
//suo dian
for(int i = ; i <= n; i++)vis[i]=;
for(int i = ; i <= m; i++){
int x = edge[i].fst;
int y = edge[i].sc;
x = color[x];
y = color[y];
if(x!=y){
v[x].pb(y);
in[y]++;
out[x]++;
}
}
int In=;
int Ou=;
for(int i = ; i <= sum; i++){
if(in[i]==)In++;
if(out[i]==)Ou++;
}
int ans = max(In,Ou);
if(ans==)ans--;
printf("%d\n",ans); }
return ;
}
/*
4 3
1 2
2 3
4 3 4 3
1 2
2 3
3 4 8 6
1 2
1 3
1 5
3 4
3 6
6 7 6 5
1 2
2 3
3 1
3 5
1 4 2 2
1 2
2 1 3 3
1 2
2 3
1 3 7 6
1 2
2 3
1 3
4 5
4 6
4 7 4 5
1 2
1 3
1 4
2 3
3 4 4 5
1 2
1 3
1 4
2 3
4 3 3 1
1 2
*/