Strongly connected HDU - 4635 原图中在保证它不是强连通图最多添加几条边

1 //题意：
2 //给你一个有向图，如果这个图是一个强连通图那就直接输出-1
3 //否则，你就要找出来你最多能添加多少条边，在保证添加边之后的图依然不是一个强连通图的前提下
4 //然后输出你最多能添加的边的数目
5 //
6 //题解：
7 //1、判断是否是强连通图你可以看一下有几个点的low[x]==dfn[x]，如果只有一个，那这个图就是一个强连通图
8 //2、
9 //假如我们有两个子图，我们可以让这两个子图中每一个图内都连上有向边(把子图内部连成完全图)。然后再在这两个子图之间连上一条有向边
10 //这样的话它仍然不是一个强连通图，因为这两个图之间的边只能进不能出(即，图与图之间是用单向边连接的)
11 //这个子图是什么？
12 //这个子图就是缩点之后的点的数目，因为缩点之后肯定可以保证里面没有环。但是这个点可能是由许多点缩成的，这个点
13 //内部就是一个子图，除了这个点之外所有点是另一个子图。
14 //之后我们可以先让原图进行缩点，这样图中就没有了环，然后我们再找出来哪个点的出度等于1或者入读等于1
15 //因为只有这样的点才是决定是否这个图能变成强连通图的关键
16 //为什么要找出入或者入度为0的点，因为作为一个强连通图是没有任何一个点出度或入度为0(反证法)
17 #include<stdio.h>
18 #include<string.h>
19 #include<iostream>
20 #include<algorithm>
21 #include<map>
22 #include<math.h>
23 #include<set>
24 #include<vector>
25 #include<queue>
26 using namespace std;
27 typedef long long ll;
28 const int maxn=100005;
29 const int mod=26;
30 const int INF=0x3f3f3f3f;
31 const int block=300;
32 struct edge
33 {
34 ll u,v,next;
35 } e[100005];
36 ll dfn[maxn],low[maxn],stacks[maxn],belong[maxn],in[maxn],out[maxn],g[maxn];
37 ll head[maxn],visit[maxn],cnt,tot,index,scc;
38 void init()
39 {
40 memset(in,0,sizeof(in));
41 memset(out,0,sizeof(out));
42 memset(g,0,sizeof(g));
43 memset(head,-1,sizeof(head));
44 memset(low,0,sizeof(low));
45 memset(dfn,0,sizeof(dfn));
46 memset(visit,0,sizeof(visit));
47 memset(belong,0,sizeof(belong));
48 cnt=tot=index=scc=0;
49 }
50 void add_edge(ll x,ll y)
51 {
52 e[cnt].u=x;
53 e[cnt].v=y;
54 e[cnt].next=head[x];
55 head[x]=cnt++;
56 }
57 ll tarjan(ll x)
58 {
59 dfn[x]=low[x]=++tot;
60 stacks[++index]=x;
61 visit[x]=1;
62 for(ll i=head[x]; i!=-1; i=e[i].next)
63 {
64 if(!dfn[e[i].v])
65 {
66 tarjan(e[i].v);
67 low[x]=min(low[x],low[e[i].v]);
68 }
69 else if(visit[e[i].v])
70 {
71 low[x]=min(low[x],dfn[e[i].v]);
72 }
73 }
74 if(dfn[x]==low[x])
75 {
76 scc++;
77 do
78 {
79 g[scc]++;
80 visit[stacks[index]]=0;
81 belong[stacks[index]]=scc;
82 index--;
83 }
84 while(x!=stacks[index+1]);
85 }
86 }
87 int main()
88 {
89 ll n,m,t,p=0;
90 scanf("%lld",&t);
91 while(t--)
92 {
93 init();
94 scanf("%lld%lld",&n,&m);
95 cnt=0;
96 for(ll i=1; i<=n; ++i)
97 {
98 head[i]=-1;
99 visit[i]=0;
100 dfn[i]=0;
101 low[i]=0;
102 }
103 ll mm=m;
104 while(mm--)
105 {
106 ll x,y;
107 scanf("%lld%lld",&x,&y);
108 add_edge(x,y);
109 }
110 ll flag=0;
111 for(ll i=1;i<=n;++i)
112 {
113 if(!dfn[i])
114 tarjan(i);
115 }
116 if(scc==1)
117 {
118 printf("Case %lld: -1\n",++p);
119 }
120 else
121 {
122 for(ll i=0; i<cnt; ++i)
123 {
124 ll fx=belong[e[i].u];
125 ll fy=belong[e[i].v];
126 if(fx!=fy)
127 {
128 out[fx]++;
129 in[fy]++;
130 }
131 }
132 ll ans=0,sum=0;
133 for(ll i=1; i<=scc; ++i)
134 {
135 if(in[i]==0 || out[i]==0)
136 {
137 sum=0;
138 //printf("%lld**\n",g[i]);
139 ll temp=n-g[i];
140 //printf("%lld*\n",temp);
141 sum+=temp*(temp-1);
142 //printf("%lld**\n",sum);
143 sum+=g[i]*(g[i]-1);
144 //printf("%lld***\n",sum);
145 sum+=g[i]*temp;
146 //printf("%lld****\n",sum);
147 sum-=m;
148 ans=max(ans,sum);
149 }
150
151 }
152 printf("Case %lld: %lld\n",++p,ans);
153 }
154 }
155 return 0;
156 }