G - Strongly connected（连通图）

G - Strongly connected（连通图）

题目大意：给你n个点，m条边（有向边），问：最多再加多少条边，使得该图不是一个强连通图。

思路：当初我想的是找出缩点之后，点数（x）最少的缩点，那么剩下的点就是y=n-x,这y个点组成一个强连通图，x个的缩点，每一个向y个点作一条边，这样x*(x-1)+y*(y-1)+x*y-m就是答案。
但是一直wr，因为你找的缩点可能入度或出度不一定为零，这样不能做一个方向的边（要么都为出边，要么都为入边），后来看完题解发现要找入度或者出度为0的缩点，找出包含个数最小（x）的缩点，剩下的点就是y=n-x，答案就是x*(x-1)+y*(y-1)+x*y-m。

详见代码：

#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1e5+9;
int firs[maxn],low[maxn],DFN[maxn],sccnow[maxn],sccinq[maxn],out[maxn],in[maxn];
int dfs_clock,scc_clock,N;
stacks;
struct node
{
    int u,v,nex;
} edge[maxn];

void build_edge(int u,int v)//建边
{
    edge[N]=(node)
    {
        u,v,firs[u]
    };
    firs[u]=N++;
}
void init()//初始化
{
    memset(firs,-1,sizeof(firs));
    memset(low,0,sizeof(low));
    memset(DFN,0,sizeof(DFN));
    memset(sccnow,0,sizeof(sccnow));
    memset(sccinq,0,sizeof(sccinq));
    memset(out,0,sizeof(out));
    memset(in,0,sizeof(in));
    scc_clock=dfs_clock=N=0;
    while(!s.empty())s.pop();
}
void Trajan(int u)//Trajan缩点
{
    low[u]=DFN[u]=++dfs_clock;
    s.push(u);
    for(int i=firs[u];~i;i=edge[i].nex)
    {
        int v=edge[i].v;
        if(!DFN[v])
        {
            Trajan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!sccnow[v])
            low[u]=min(low[u],DFN[v]);
    }
    if(low[u]==DFN[u])
    {
        scc_clock++;
        while(1)
        {
            int x=s.top();
            s.pop();
            sccnow[x]=scc_clock;
            sccinq[scc_clock]++;
            if(u==x) break;
        }
    }
}
int main()
{
    int t,n,m,tt=1;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=0; i