HDU 4635

问题:

给定一个有向图,问最多添加多少边后,该图仍然不是强连通图?

如果已经是强连通图则输出-1

思路:

1. 在每个强连通子图中添加边不影响该图变成强连通图(所以可以任意添加).那么将强连通子图缩成点来分析

2. 保证不变成强连通图,那么合并到只剩下2个强连通子图(点),且2点间只存在单向边（单向边说明点的入度或出度=0）能够使得添加的边最多

   证明:

   • 如果剩下3个强连通子图(点),必然能够添加边继续缩点.那么最后肯定还是剩下2个强连通子图(点).且入度/出度=0

3. 整个强连通子图添加边后变成完全子图. 通过点的个数来求边的个数.

---

• 设x 为第一个强连通子图中点的个数,则y为第二个.x+y=n(题目所有点).2个完全子图的边有$edge_1=x*(x-1)+y*(y-1) $
• 2点(强连通子图)之间只存在单向边.那么$edge_2=x*y$
• 减去题目已经给出的m条边就是添加最多的边的条数

---

$ans = edge_1+edge_2 = xy+x(x-1)+y*(y-1)-m$

$ans = (x+y)^2+(x+y)-x*y-m$

$ans = N^2+N-x*y - m$

• 说明x与y之间差距越大添加的边越多
• 通过找到包含点最少的强联通分量来确定x的值

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1e5+10;
int n,m;

int head[maxn],next1[maxn],ver[maxn];
int dfn[maxn],low[maxn],stack_[maxn],in_stack[maxn];
int in[maxn],out[maxn],belong[maxn];
int scount[maxn];
int tot,cnt,num,top;

void add(int x,int y) {
    ver[++tot] = y;
    next1[tot] = head[x];
    head[x] = tot;
}

void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    stack_[++top] = x;
    in_stack[x] = 1;
    for (int i=head[x]; i; i=next1[i]) {
        int to = ver[i];
        if (!dfn[to]) {
            tarjan(to);
            low[x] = min(low[x],low[to]);
        } else if (in_stack[to])
            low[x] = min(low[x],dfn[to]);
    }
    if (dfn[x] == low[x]) {
        cnt++;
        int y;
        do{
            y = stack_[top--];
            belong[y] = cnt;
            in_stack[y] = 0;
            scount[cnt]++;
        } while(y != x);
    }
}

void init() {
    tot = cnt = num= top  = 0;
    memset(head,0,sizeof head);
    memset(ver,0,sizeof ver);
    memset(next1,0,sizeof next1);
    memset(in_stack,0,sizeof in_stack);
    memset(stack_,0,sizeof stack_);
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    memset(in,0,sizeof in);
    memset(out,0,sizeof out);
    memset(belong,0,sizeof belong);
    memset(scount,0,sizeof scount);
}

int main() {
    freopen("1.in","r",stdin);
    int times; cin >> times;
    for (int _times=1; _times<=times; ++_times) {
        init();
        scanf("%d%d",&n,&m);
        for (int i=1; i<=m; ++i) {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
        }
        for (int i=1; i<=n; ++i)
            if(!dfn[i])
                tarjan(i);
        if (cnt == 1) {
            printf("Case %d: -1\n",_times);
            continue;
        }
        for (int i=1; i<=n; ++i)
            for (int j=head[i]; j;j=next1[j]) {
                int to = ver[j];
                if (belong[i] != belong[to]) {
                    in[belong[to]]++;
                    out[belong[i]]++;
                    /*cout << " a= " << belong[i] << " b= " << belong[to] << endl;*/
                }
            }
        int x = 0x3f3f3f3f;
        for (int i=1; i<=cnt; ++i) {
            if (!in[i]) { x = min(x,scount[i]); }
            if (!out[i]) { x = min(x,scount[i]); }
        }
        printf("Case %d: %d\n",_times,n*n-n-x*(n-x)-m);
    }
    return 0;
}