HDU4635

/*

最终添加完边的图，肯定可以分成两个部X和Y，其中只有X到Y的边没有Y到X的边，

那么要使得边数尽可能的多，则X部肯定是一个完全图，Y部也是，

同时X部中每个点到Y部的每个点都有一条边，假设X部有x个点，

Y部有y个点，有x+y=n，同时边数F=x*y+x*(x-1)+y*(y-1)，整理得：F=N*N-N-x*y，

当x+y为定值时，二者越接近，x*y越大，所以要使得边数最多，那么X部和Y部的点数的个数差距就要越大，

所以首先对于给定的有向图缩点，对于缩点后的每个点，如果100它的出度或者入度为0，那么它才有可能成为X部或者Y部，

所以只要求缩点之后的出度或者入度为0的点中，包含节点数最少的那个点，令它为一个部，其它所有点加起来做另一个部，

就可以得到最多边数的图了

*/

/*奶奶个熊的，一定能AC*/

/*PS：加了这句话骂他，居然还AC，果然机器是没有人性的，第一次看了一晚上的tarjan，照着敲了代码，以后加强，睡觉......*/

/*tarjan学习：https://www.byvoid.com/blog/scc-tarjan*/

#include<stdio.h>

#include<string.h>

const int maxn=+;

int per[maxn],lowlink[maxn],scc[maxn],st[maxn];

int index1[maxn],index2[maxn],vis[maxn];

int t1,t2,sccn,top,n,m,dfsn,ans;

struct point

{

    int s,t;

    int next;

}e[maxn];

struct Nnode

{

    int fn,tn;

    int num;

}node[maxn];

int min(int a,int b)

{

    if(a<b) return a;

    return b;

}

void init()

{

    memset(per,,sizeof(per));

    memset(scc,,sizeof(scc));

    memset(lowlink,,sizeof(lowlink));

    memset(st,,sizeof(st));

    memset(vis,,sizeof(vis));

    memset(index1,-,sizeof(index1));

    memset(index2,-,sizeof(index2));

    dfsn=sccn=top=ans=t1=t2=;

}

void ad1(int s,int t)

{

    e[t1].s=s;

    e[t1].t=t;

    e[t1].next=index1[s];

    index1[s]=t1++;

}

void ad2(int s,int t)

{

    e[t2].s=s;

    e[t2].t=t;

    e[t2].next=index1[s];

    index1[s]=t2++;

}

void dfs(int u)//tarjan找强连通分量

{

    int i;

    per[u]=lowlink[u]=++dfsn;

    st[top++]=u;

    vis[u]=;

    for(i=index1[u];i!=-;i=e[i].next)

    {

        int v=e[i].t;

        if(!per[v])

        {

            dfs(v);

            lowlink[u]=min(lowlink[u],lowlink[v]);

        }

        else if(!scc[v])

        lowlink[u]=min(lowlink[u],per[v]);

    }

    if(lowlink[u]==per[u])

    {

        int k=;

        sccn++;

        for(;;)

        {

            int x=st[--top];

            scc[x]=sccn;

            k++;

            if(x==u)

            break;

        }

        node[sccn].num=k;//记录缩点后的信息

        node[sccn].fn=;

        node[sccn].tn=;

    }

}

void work()

{

      int i;

      for(i=;i<=n;i++)

          if(!vis[i])

              dfs(i);

          if(sccn==)

          {

              ans=-;

              return;

          }

    for(i=;i<t1;i++) //缩点后重新建图

    {

      int u=scc[e[i].s];

      int v=scc[e[i].t];

      ad2(u,v);

      if(u!=v)  //不在同一个强连通分量中

      {

        node[u].tn++;

        node[v].fn++;

      }

    }

    int Min=,sum=;

    for( i=;i<=sccn;i++)

    {

        if(node[i].fn==||node[i].tn==)

        {

         if(Min>node[i].num)

          Min=node[i].num;

        }

        sum+=node[i].num;

    }

    ans=sum*sum-sum-Min*(sum-Min)-m;

}

int main()

{

    int k=;

    int t;

    int u,v,i;

    scanf("%d",&t);

    while(t--)

    {

        init();

        scanf("%d%d",&n,&m);

        for(i=;i<=m;i++)

        {

            scanf("%d%d",&u,&v);

            ad1(u,v);

        }

        work();

        printf("Case %d: %d\n",++k,ans);

    }

    return ;

}