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+;

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<<],g[N<<];

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]=;

    s.push(u);

    for(int i=head[u];i!=-;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=;

    while(t--){

        Case++;

        memset(head,-,sizeof(head));tot=;

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

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

            int u,v;

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

            g[i].u=u;g[i].v=v;

            adde(u,v);

        }

        memset(dfn,,sizeof(dfn));

        memset(scc,,sizeof(scc));T=;

        memset(vis,,sizeof(vis));cc=;

        memset(num,,sizeof(num));

        memset(in,,sizeof(in));

        memset(out,,sizeof(out));

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

            if(!vis[i]) Tarjan(i);

        }

        printf("Case %d: ",Case);

        if(cc==){

            puts("-1");

            continue ;

        }

        for(int i=;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-)-m;

        ll ans = ;

        for(int i=;i<=cc;i++){

            if(!in[i] || !out[i]) ans=max(ans,tmp-num[i]*(n-num[i]));

        }

        cout<<ans<<endl;

    }

    return ;

}

巴特西

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

Strongly connected

最新文章

热门文章