学步园

求加几条边可以使原图成一个强连通分量

思路：先求出强连通分量个数，再求出每个强连通分量的入度，出度

入度为0的个数和出度为0的个数，最大的那个就是要加的边

#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std;
#define N 20001
#define inf 0x3fffffff
int n,m,OP;
int belong[N],dfs[N],low[N],ins[N],in[N],out[N];
struct op
{
	int end;
	struct op *next;
}*e[50002];
void addeage(int x,int y)
{
	struct op *q=new op;
	q->end=y;
	q->next=e[x];
	e[x]=q;
}
stack<int>Q;
int ans,idx;
void Tarjan(int x)
{
	int v;
	dfs[x]=low[x]=idx++;
	Q.push(x);
	ins[x]=1;
	for(op *j=e[x];j;j=j->next)
	{
		if(dfs[j->end]==-1)
		{
			Tarjan(j->end);
			low[x]=low[x]>low[j->end]?low[j->end]:low[x];
		}
		else if(ins[j->end]==1)
			low[x]=low[x]>dfs[j->end]?dfs[j->end]:low[x];
	}
	if(low[x]==dfs[x])
	{
		ans++;
		while(1)
		{
			v=Q.top();
			Q.pop();
			ins[v]=0;
			belong[v]=ans;
			if(v==x)break;
		}
		
	}
}
int main()
{
	int i,j,x,y,z,t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		OP=0;
		for(i=0;i<=n;i++)
		{
			e[i]=NULL;
			dfs[i]=-1;
			ins[i]=0;
			out[i]=0;
			in[i]=0;
		}
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&x,&y);
			addeage(x,y);
		}
		ans=idx=0;
		for(i=1;i<=n;i++)
		{
			if(dfs[i]==-1)
				Tarjan(i);
		}
		if(ans==1)
		{
			printf("0\n");
			continue;
		}
		for(i=1;i<=n;i++)
		{
			for(op *j=e[i];j;j=j->next)
			{
				if(belong[i]!=belong[j->end])
				{
					in[belong[j->end]]++;
					out[belong[i]]++;
				}
			}
		}
		int OP1=0;
		for(i=1;i<=ans;i++)
		{
			if(in[i]==0)
				OP1++;
			if(out[i]==0)
				OP++;
		}
		if(OP<OP1)
			OP=OP1;
		printf("%d\n",OP);
	}
	return 0;
}