Strongly connected

强连通分量

我们利用强连通分量进行缩点。然后找入度为0或者出度为0的点。
他们其中一个一定是在我们最终的图中被孤立的点。

为什么要这样说呢？
因为你仔细想想啊。假如我没有边，我让你用最多的边连出一个不是强连通分量的图
你是不是孤立一个点，使他只有出度没有入度或者只有入度没有出度？
那，这里不也是一样的吗？！其实，顺着感觉走就可以了。
然后我们统计就可以了。我们想对于一个出度为零或者入度为零的点，孤立他得到的最大收益应该为：
n(n-1)-m-cnt[i](n-cnt[i]) cnt[i]指该连通块中的点的数量。
这里用的是割补法求的，刚开始我想直接求，麻烦得很。。。。。。。。
我们注意到，这个式子里面只有一个变量cnt[i]
设为x把他单独出出来看：x^2-n*x 对称轴为n/2
我们可以直接根据这个式子判断，但是其实我们直接取最小值就好了。
因为有一个点数为k的连通块那么就必定会有一个点数为n-k的连通块。而二者是相等的！

不细心，wa了好多发:(

代码如下：

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long ll;
const int max_m = 2e5 + 100;
const int max_n = 1e5 + 100;
struct edge{
    int to, next;
}E[max_m];
int head[max_n];
int cnt = 1;
void add(int from, int to) {
    E[cnt].to = to;
    E[cnt].next = head[from];
    head[from] = cnt++;
}

int cct[max_n];
stack<int> st;int tot = 0;
int dfn[max_n], low[max_n];
int col[max_n];int color = 0;
void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    st.push(u);
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (col[v] == 0)low[u] = min(low[u], dfn[v]);
    }if (low[u] != dfn[u])return;
    ++color;
    while (st.top() != u) {
        col[st.top()] = color;
        st.pop();
        ++cct[color];
    }col[st.top()] = color;
    st.pop();++cct[color];
}
int in[max_n], out[max_n];
int N, M;
int main() {
    int T;scanf("%d", &T);
    for (int tcase = 1;tcase <= T;++tcase) {
        scanf("%d %d", &N, &M);
        fill(head, head + N + 10, 0);cnt = 1;
        fill(dfn, dfn + N + 10, 0);
        fill(col, col + N + 10, 0);
        fill(cct, cct + N + 10, 0);
        fill(in, in + N + 10, 0);
        fill(out, out + N + 10, 0);
        color = tot = 0;
        for (int i = 1, u, v;i <= M;++i) {
            scanf("%d %d", &u, &v);
            add(u, v);
        }for (int i = 1;i <= N;++i)
            if (!dfn[i])
                tarjan(i);
        if (color == 1) {
            printf("Case %d: -1\n", tcase);
            continue;
        }for (int u = 1;u <= N;++u) {
            for (int i = head[u];i;i = E[i].next) {
                int v = E[i].to;
                if (col[v] == col[u])continue;
                ++in[col[v]];++out[col[u]];
            }
        }
        ll ans = 0;ll tmp = N;
        for (int i = 1;i <= color;++i)
            if (in[i] == 0 || out[i] == 0)
                tmp = min(tmp, (ll)cct[i]);
        ans = (ll)N * ((ll)N - 1) - ((ll)N - tmp) * tmp - M;
        printf("Case %d: %lld\n", tcase, ans);
    }
}