hdu_4635 Strongly connected

题目:

  Give a simple directed graph with N nodes and M edges. Please tell me the maximum number of the edges you can add that the graph is still a simple directed graph. Also, after you add these edges, this graph must NOT be strongly connected.
  A simple directed graph is a directed graph having no multiple edges or graph loops.
  A strongly connected digraph is a directed graph in which it is possible to reach any node starting from any other node by traversing edges in the direction(s) in which they point.

思路:

  先对整幅图缩点。因为强联通块不存在出/入度为的点,那么可以考虑枚举一个出/入度为的点,只要不使这个点被破坏,剩下的边可以随意连。
  那么设保留的点为,考虑能连的最大边数。为联通块点的个数,为块内边的个数,为入度,为出度。
  外互相连接:
  内相互连接:
  内外连接:
  把这三个加起来即可。

代码:

#include <bits/stdc++.h>
#define MN 100005
#define ll long long
#define clr(a,b) memset(a,b,sizeof a)
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
using namespace std;
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void clear(){clr(HEAD,0);tot=0;}
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
    #define EOR(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
};
Link<MN,MN,int> G;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
int siz[MN],stk[MN],tp,ble[MN],dfn[MN],low[MN],bcnt,No;
void dfs(int o){
    dfn[o]=low[o]=++No;
    stk[++tp]=o;
    EOR(k,G,o){
        int v=G[k];
        if(!dfn[v]){
            dfs(v);
            tomin(low[o],low[v]);
        }
        else if(!ble[v])tomin(low[o],dfn[v]);
    }
    if(dfn[o]==low[o]){
        bcnt++;
        do {
            ble[stk[tp]]=bcnt;
            siz[bcnt]++;
        }while(stk[tp--]!=o);
    }
}
int ecnt[MN],ind[MN],outd[MN],n;
void rebuild(){
    FOR(o,1,n)EOR(k,G,o){
        int v=G[k];
        if(ble[v]==ble[o])ecnt[ble[o]]++;
        else ind[ble[o]]++,outd[ble[v]]++;
    }
}
void clear(){
    clr(ind,0);clr(outd,0);
    clr(dfn,0);clr(ble,0);
    clr(siz,0);G.clear();
    clr(ecnt,0);
    bcnt=0;No=0;
}
int m;
ll calc(int o){
    ll ans=0;
    ans+=(ll)(n-siz[o])*(n-siz[o]-1)-m+outd[o]+ind[o]+ecnt[o];
    ans+=(ll)(n-siz[o])*siz[o]-outd[o]-ind[o];
    ans+=(ll)siz[o]*(siz[o]-1)-ecnt[o];
    return ans;
}
int main(){
    int T;
    scanf("%d",&T);
    FOR(t,1,T){
        clear();
        scanf("%d%d",&n,&m);
        for(int i=1,a,b;i<=m;i++){
            scanf("%d%d",&a,&b);
            G.add(a,b);
        }
        FOR(i,1,n)if(!dfn[i])
            dfs(i);
        if(bcnt==1){
            printf("Case %d: -1\n",t);
            continue;
        }
        rebuild();
        ll ans=0;
        FOR(o,1,bcnt)if(!outd[o]||!ind[o])
            tomax(ans,calc(o));
        printf("Case %d: %lld\n",t,ans);
    }
    return 0;
}