题意
给定一个N个点M条边的简单图，求最多能加几条边，使得这个图仍然不是一个强连通图。
思路
2013多校第四场1004题。和官方题解思路一样，就直接贴了~
最终添加完边的图，肯定可以分成两个部X和Y，其中只有X到Y的边没有Y到X的边，那么要使得边数尽可能的多，则X部肯定是一个完全图，Y部也是，同时X部中每个点到Y部的每个点都有一条边，假设X部有x个点，Y部有y个点，有x+y=n，同时边数F=x*y+x*(x-1)+y*(y-1)，整理得：F=N*N-N-x*y，当x+y为定值时，二者越接近，x*y越大，所以要使得边数最多，那么X部和Y部的点数的个数差距就要越大，所以首先对于给定的有向图缩点，对于缩点后的每个点，如果它的出度或者入度为0，那么它才有可能成为X部或者Y部，所以只要求缩点之后的出度或者入度为0的点中，包含节点数最少的那个点，令它为一个部，其它所有点加起来做另一个部，就可以得到最多边数的图了
代码
#include
#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)/2)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXN = 10005;
const int MAXM = 50005;
struct SCC{
int scc_num, scc[MAXN]; //强连通分量总数、每个节点所属的强连通分量
int scc_acount[MAXN]; //每个强连通分量的节点个数
int dfn[MAXN], low[MAXN], id;
stack st;
bool vis[MAXN], instack[MAXN];
int cnt, head[MAXN];
struct node{
int u, v;
int next;
}arc[MAXM];
void init(){
cnt = 0;
mem(head, -1);
return ;
}
void add(int u, int v){
arc[cnt].u = u;
arc[cnt].v = v;
arc[cnt].next = head[u];
head[u] = cnt ++;
}
void dfs(int u){
vis[u] = instack[u] = 1;
st.push(u);
dfn[u] = low[u] = ++ id;
for (int i = head[u]; i != -1; i = arc[i].next){
int v = arc[i].v;
if (!vis[v]){
dfs(v);
low[u] = min(low[u], low[v]);
}
else if (instack[v]){
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]){
++ scc_num;
while(st.top() != u){
scc[st.top()] = scc_num;
scc_acount[scc_num] ++;
instack[st.top()] = 0;
st.pop();
}
scc[st.top()] = scc_num;
scc_acount[scc_num] ++;
instack[st.top()] = 0;
st.pop();
}
return ;
}
void tarjan(int n){
mem(scc_acount, 0);
mem(vis, 0);
mem(instack, 0);
mem(dfn, 0);
mem(low, 0);
mem(scc, 0);
id = scc_num = 0;
while(!st.empty())
st.pop();
for (int i = 1; i <= n; i ++){ //枚举节点
if (!vis[i])
dfs(i);
}
return ;
}
}S;
/* ------------------------------ Tarjan ------------------------- */
int ca;
int odeg[MAXN];
int ideg[MAXN];
void solve(int n, int m){
mem(odeg, 0);
mem(ideg, 0);
S.tarjan(n);
if (S.scc_num == 1){
printf("Case %d: %d
", ca, -1);
return ;
}
for (int i = 0; i < S.cnt; i ++){
int u = S.arc[i].u;
int v = S.arc[i].v;
if (S.scc[u] != S.scc[v]){
odeg[S.scc[u]] ++;
ideg[S.scc[v]] ++;
}
}
long long maxn = 0;
for (int i = 1; i <= S.scc_num; i ++){
if (ideg[i] == 0 || odeg[i] == 0){
long long remain_num = n - S.scc_acount[i];
long long num = (long long)S.scc_acount[i]*(S.scc_acount[i]-1) + (long long)remain_num*(remain_num-1) + (long long)remain_num*S.scc_acount[i] - m;
if (num > maxn){
maxn = num;
}
}
}
printf("Case %d: %I64d
", ca, maxn);
}
int main(){
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
int t;
scanf("%d", &t);
for (ca = 1; ca <= t; ca ++){
int n, m;
scanf("%d %d", &n, &m);
S.init();
for (int i = 0; i < m; i ++){
int u, v;
scanf("%d %d", &u, &v);
S.add(u, v);
}
solve(n, m);
}
return 0;
}