HDU 4635 Strongly connected (强连通分量)

题意

给定一个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  maxn){
                maxn = num;
            }
        }
    }
    printf("Case %d: %I64d\n", ca, maxn);
}
int main(){
	//freopen("test.in", "r", stdin);
	//freopen("test.out", "w", stdout);
	int t;
	scanf("%d", &t);
	for (ca = 1; ca