kuangbin专题专题九连通图 Strongly connected HDU

题目链接：https://vjudge.net/problem/HDU-4635

题目：有向图，给定若干个连通图，求最多还能添加几条边，添完边后，图仍然要满足

（1）是简单图，即没有重边或者自环

（2）不是有向强连通图

思路：我们可以这么想，n个顶点，一个有向图边数最多，就是有向完全图，则边数为n*(n-1)。

要满足不是强连通图，我们可以假设有一个tarjan缩成的点（scc），它不能到达其他所有点，或者其他所有点

不能到达它，假设这个scc有k个顶点，也就是说，k*(n-k)条边是不存在的，那么最大添加边数应该是 n*(n-1) - k*(n-k) - m(本来有的边) ---- ①

给定的图情况不确定，我们先进行tarjan缩点，分成若干个scc，每个scc中也记录各自scc中的顶点数，然后进行scc的入度出度统计。

为使添加的边能最多，我们选所有的入度为0或者出度为0的scc 套入公式①，选最大即可。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 const int N = (int)1e5+;

 int n,m,tot,tim,scc,top;

 int head[N],dfn[N],low[N],scc_no[N],s[N],ins[N];

 struct node{

     int to;

     int nxt;

 }e[N];

 struct col{

     int ru;

     int chu;

     int cnt;

 }col[N];//强连通分量

 void init(){

     for(int i = ; i <= n; ++i){

         head[i] = -;

         col[i].ru = col[i].chu = dfn[i] = ;

     }

     tot = tim = scc = ;

 }

 inline void add(int u,int v){

     e[tot].to = v;

     e[tot].nxt = head[u];

     head[u] = tot++;

 }

 void tarjan(int now,int pre){

     dfn[now] = low[now] = ++tim;

     ins[now] = ; s[top++] = now;

     int to;

     for(int o = head[now]; ~o; o = e[o].nxt){

         to = e[o].to;

      //   if(to == pre) continue;

         if(!dfn[to]){

             tarjan(to,now);

             low[now] = min(low[now],low[to]);

         }

         else if(ins[to]) low[now] = min(low[now],dfn[to]);

     }

     if(dfn[now] == low[now]){

         int x,cnt = ;

         ++scc;

         do{

             x = s[--top];

             ins[x] = ;

             scc_no[x] = scc;

             ++cnt;

         }while(now != x);

         col[scc].cnt = cnt;//每个强连通分量包含几个点

     }

 }

 //入度出度统计

 void du_cnt(){

     int to;

     for(int now = ; now <= n; ++now){

         for(int o = head[now]; ~o; o = e[o].nxt){

             to = e[o].to;

             if(scc_no[to] == scc_no[now]) continue;

                 ++col[scc_no[to]].ru;

                 ++col[scc_no[now]].chu;

         }

     }

 }

 void solve(int _case){

     for(int i = ; i <= n; ++i)

         if(!dfn[i]) tarjan(i,i);

     ll ans = (ll)n*(n-) - m;

     ll useless = (1LL) << ;

     du_cnt();

     for(int i = ; i <= scc; ++i){

         if(!col[i].ru || !col[i].chu){

             useless = min(useless,(ll)col[i].cnt*(n-col[i].cnt));

         }

     }

     if(scc == ) printf("Case %d: -1\n",_case);

     else printf("Case %d: %lld\n",_case,ans-useless);

 }

 int main(){

     int T,u,v;

     scanf("%d",&T);

     for(int i = ; i <= T; ++i){

         scanf("%d%d",&n,&m);

         init();

         for(int x = ; x <= m; ++x){

             scanf("%d%d",&u,&v);

             add(u,v);

         }

         solve(i);

     }

     return ;

 }

巴特西

kuangbin专题专题九连通图 Strongly connected HDU - 4635

最新文章

热门文章

巴特西

kuangbin专题 专题九 连通图 Strongly connected HDU - 4635

最新文章

热门文章

kuangbin专题专题九连通图 Strongly connected HDU - 4635