2015
09-17

# 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;
}



,