首页 > 代码库 > hdu 4635(强连通+缩点)

hdu 4635(强连通+缩点)

2024-07-04 10:21:53   230人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4635

Strongly connected

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


Problem 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
3
3 3
1 2
2 3
3 1
3 3
1 2
2 3
1 3
6 6
1 2
2 3
3 1
4 5
5 6
6 4
 

Sample Output
Case 1: -1
Case 2: 1
Case 3: 15
 

Source
2013 Multi-University Training Contest 4
 

Recommend
zhuyuanchen520   |   We have carefully selected several similar problems for you:  4822 4821 4820 4819 4818 
 

Statistic | Submit | Discuss | Note

这题不难，不过以前图论算法接触得不是太多。。。都是泪。。

采用tarjon + 缩点可以比较快的解出来，算是模板题

处理完后的图，可以分成 X和Y 两部分，其中X，Y之间只存在X到Y的边。

要使得边数尽可能多，则X，Y必为完全图。X的每点到Y的每点必有一条边。

x,y 分别为X,Y的点数，则x+y=n.

ans=x*y+x*(x-1)+y*(y-1)-m 即为答案，找出最大值即可

对那些强连通分量进行缩点，则只有它的出度或入度为0，才有可能成为X或Y部。

//Tarjan algorithm
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
using namespace std;
const int MAX=100005;
vector<int> G[MAX];
stack<int> st;
int dnf[MAX],low[MAX],belong[MAX],instack[MAX],sum[MAX],dep,num;
int in[MAX],out[MAX];
void tarjan(int x)
{
    dnf[x]=low[x]=dep++;
    instack[x]=1;
    st.push(x);
    for(int i=0;i<G[x].size();i++)
    {
        int y=G[x][i];
        if(!dnf[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(instack[y])
        {
            low[x]=min(low[x],dnf[y]);
        }
    }
    if(dnf[x]==low[x])
    {
        int y=-1;
        while(y!=x)
        {
            y=st.top();
            st.pop();
            belong[y]=num;
            instack[y]=0;
            sum[num]++;
        }
        num++;
    }
}
void init()
{
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    memset(dnf,0,sizeof(dnf));
    memset(low,0,sizeof(low));
    memset(belong,0,sizeof(belong));
    memset(sum,0,sizeof(sum));
    memset(instack,0,sizeof(instack));
    for(int i=0;i<MAX;i++) G[i].clear();
    while(!st.empty()) st.pop();
    num=0;
    dep=1;
}
int main()
{
    int T;
    while(cin>>T)
    {
        for(int kase=1;kase<=T;kase++)
        {
            int n,m;
            cin>>n>>m;
            init();
            for(int i=0;i<m;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                G[x].push_back(y);
            }
            for(int i=1;i<=n;i++)
                if(!dnf[i])
                    tarjan(i);
            if(num==1)
            {
                printf("Case %d: -1\n",kase);
                continue;
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=0;j<G[i].size();j++)
                {
                    if(belong[i]!=belong[G[i][j]])
                    {
                        out[belong[i]]++;
                        in[belong[G[i][j]]]++;
                    }
                }
            }
            __int64 ans=0,tmp;
            for(int i=0;i<num;i++)
            {
                if(in[i]==0||out[i]==0)
                {
                    tmp=sum[i];
                    ans=max(ans,tmp*(tmp-1)+(n-tmp)*(n-tmp-1)+tmp*(n-tmp)-m);
                }
            }
            printf("Case %d: ",kase);
            cout<<ans<<endl;
        }
    }
    return 0;
}





联系
我们