HDU4625:Strongly connected（思维+强连通分量）

Strongly connected

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4765 Accepted Submission(s): 1880

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4635

Description:

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.

Input:

The first line of date is an integer T, which is the number of the text cases.
Then T cases follow, each case starts of two numbers N and M, 1<=N<=100000, 1<=M<=100000, representing the number of nodes and the number of edges, then M lines follow. Each line contains two integers x and y, means that there is a edge from x to y.

Output:

For each case, you should output the maximum number of the edges you can add.
If the original graph is strongly connected, just output -1.

Sample Input:

Sample Output:

Case 1: -1
Case 2: 1
Case 3: 15

题意：

给出一个有向图，保证图中无重边。现在要求加尽量多的边，使得最终的图不是强连通的，即任意两点可以互相到达，并且图中无重边。

题解：

可以想到，最终的图是一个二部图，设左边这部分为X，右边这部分为Y，那么X,Y之间只有单向边，同时X,Y中所有点都是强连通的，此时满足条件。

现在的问题就是这么确定这个X,Y。假设X中有x个点，同理，Y中有y个点，然后来计算一波：

此时图中的边数为x*(x-1)+y*(y-1)+x*y=x²+y²+x*y-x-y=(x+y)²-x*y-x-y=n²-n-x*y。现在要使得边数最大，那么x*y就尽量小，又因为x+y为定值，那么要么x尽可能小，要么y尽可能小就是了。

然后由于图中可能存在环，我们就先用Tarjan缩点，然后选取包含点数最少，并且出度或者入度为0的那个点作为X部，之后计算一波就行了。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
int t,n,m,tot;
int head[N],num[N],in[N],out[N];
stack <int> s;
struct Edge{
    int u,v,next;
}e[N<<1],g[N<<1];
void adde(int u,int v){
    e[tot].u=u;e[tot].v=v;e[tot].next=head[u];head[u]=tot++;
}
int T,cc;
int scc[N],dfn[N],low[N],vis[N];
void Tarjan(int u){
    dfn[u]=low[u]=++T;vis[u]=1;
    s.push(u);
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(!vis[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(!scc[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        cc++;int now;
        do{
            now = s.top();s.pop();
            scc[now]=cc;
            num[cc]++;
        }while(!s.empty() && now!=u);
    }
}
int main(){
    cin>>t;
    int Case=0;
    while(t--){
        Case++;
        memset(head,-1,sizeof(head));tot=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            g[i].u=u;g[i].v=v;
            adde(u,v);
        }
        memset(dfn,0,sizeof(dfn));
        memset(scc,0,sizeof(scc));T=0;
        memset(vis,0,sizeof(vis));cc=0;
        memset(num,0,sizeof(num));
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        for(int i=1;i<=n;i++){
            if(!vis[i]) Tarjan(i);
        }
        printf("Case %d: ",Case);
        if(cc==1){
            puts("-1");
            continue ;
        }
        for(int i=1;i<=m;i++){
            int u=g[i].u,v=g[i].v;
            if(scc[u]==scc[v]) continue ;
            in[scc[v]]++;out[scc[u]]++;
        }
        ll tmp = n*(n-1)-m;
        ll ans = 0;
        for(int i=1;i<=cc;i++){
            if(!in[i] || !out[i]) ans=max(ans,tmp-num[i]*(n-num[i]));
        }
        cout<<ans<<endl;
    }
    return 0;
}