首页 > ACM题库 > HDU-杭电 > HDU 4635-Strongly connected-图-[解题报告]HOJ
2015
09-17

HDU 4635-Strongly connected-图-[解题报告]HOJ

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.

输入:

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.

输出:

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.

样例输入:

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

样例输出:

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

题意:

给你一个有向图,问你最多能添加多少条边使得这个图依然不是强联通的。

做法:

1,求出图中的所有强连通分量

2,把上述的强连通分量缩成一个点。

3,问题现在变成问一个完全图,最少需要去除多少条边使得这个图不强联通, 

       那么肯定是去除所有强联通分量中含有点数最少的点的所有进边。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stack>
#include<vector>
using namespace std;
#define maxn 100005
#define mem(a,b) memset(a,b,sizeof(a));
vector<int>q[maxn];
stack<int>qq;
int times;
int nums;
int num[maxn];
int dnf[maxn];
int low[maxn];
int out[maxn];
int in[maxn];
int sum[maxn];
int instack[maxn];
void tarjan(int x)
{
    dnf[x]=low[x]=times++;
    instack[x]=1;
    qq.push(x);
    int i;
    for(i=0;i<q[x].size();i++)
    {
        int y=q[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=qq.top();
            qq.pop();
            num[y]=nums;
            instack[y]=0;
            sum[nums]++;
        }
        nums++;
    }
    //cout<<x<<" "<<low[x]<<" "<<dnf[x]<<endl;
}
int main()
{
   // freopen("1004.in","r",stdin);
    int T,cas,i,j,n,m;
    cin>>T;
    for(cas=1;cas<=T;cas++)
    {
        cin>>n>>m;
        for(i=1;i<=n;i++)q[i].clear();
        while(!qq.empty())qq.pop();
        mem(in,0);
        mem(out,0);
        mem(dnf,0);
        mem(low,0);
        mem(num,0);
        mem(sum,0);
        mem(instack,0);
        nums=0;
        int x,y;
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            q[x].push_back(y);
        }
        for(i=1;i<=n;i++)
            if(!dnf[i])tarjan(i);
        if(nums==1)
        {
            printf("Case %d: -1\n",cas);
            continue;
        }
        for(i=1;i<=n;i++)
        {
            for(j=0;j<q[i].size();j++)
            {
                if(num[i]!=num[q[i][j]])
                {
                    out[num[i]]++;
                    in[num[q[i][j]]]++;
                }
            }
        }
        int maxx=maxn;
        for(i=0;i<nums;i++)
        {
            if(in[i]==0||out[i]==0)
            {
                if(sum[i]<maxx)maxx=sum[i];
            }
        }
        __int64 ss;
        ss=0;
        ss =(__int64)n*(n-1);
        ss-=(__int64)m;
        ss-=(__int64)maxx*(n-maxx);

        printf("Case %d: %I64d\n",cas,ss);
    }
    return 0;
}






版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/rowanhaoa/article/details/9786625


,