HDU 4635：Strongly connected（强联通 Tarjan）

太过爱你忘了你带给我的痛 2023-07-07 08:04 33阅读 0赞

# [HDU 4635：Strongly connected（强联通Tarjan）][HDU 4635_Strongly connected_Tarjan] #

一道比较经典的强联通分量题，虽然没完全搞懂，但是还是决定贴一下。

参考博客：  
[https://blog.csdn.net/u010372095/article/details/46888807][https_blog.csdn.net_u010372095_article_details_46888807]

[https://www.cnblogs.com/kuangbin/p/3230625.html][https_www.cnblogs.com_kuangbin_p_3230625.html]

**题意：**  
给定一个由n个顶点，m条边组成的有向图；求它最多可以加多少条使其不是强联通图，仍然是简单图。

**题解：**  
起初能够想到的是强联通分量+缩点；  
但是后面就真的不知道怎么办了

实则：要加边最多那么加边后的图连通分量越少越好，那么连通分量最少也就是2个。先用n个点构造一个完全图（有向图有：n\*(n-1)条边，无向图有：n\*(n-1)/2条边），再用构造的边 减去原来有的m条边=ans。再用强连通算法缩点，记录每个新点包含点的个数，从入度为0或出度为0的新点中找出包含点数最小的minnum，再用上面剩余的边ans - minnum\*(n-minnum)就是所要的答案。因为如果不减入度为0或出度为0相关的边，那么该点本身包含有入边和出边，加的边永远都是强连通图。所以只能去掉与入度为0或出度为0点的相关边，只减掉一个方向的边，要么全是（n-minnum）点数到minnum点数的入边，那么是minnum点数到(n-minnum)点数的出边。  
（以上题解参考于第一篇博客）

代码参考的kuangbin大神的代码

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const double pi=3.14159;
    const int maxn=1e5+10;
    const int maxm=1e6;
    const int mod=1e3;
    struct Edge{
        
        int next,to;
    }edge[maxn];
    int head[maxn],tot;
    int low[maxn],dfn[maxn];
    int sta[maxn];         //数组模拟栈
    int belong[maxn];      //belong[]的数组为1~scc
    int index,top;
    int scc;               //强联通分量个数
    bool inStack[maxn];     //访问数组
    int num[maxn];         //各个强联通分量包含点的个数，数组编号为1~scc
                           //num数组不一定需要，结合实际情况
    
    int in[maxn],out[maxn];           //记录入度和出度
    void addedge(int u,int v){
        
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
        return ;
    }
    void Tarjan(int u){
        
        int v;
        low[u]=dfn[u]=++index;
        sta[top++]=u;
        inStack[u]=true;
        for(int i=head[u];i!=-1;i=edge[i].next){
        
            v=edge[i].to;
            if(!dfn[v]){
        
                Tarjan(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++;
            do{
        
                v=sta[--top];
                inStack[v]=false;
                belong[v]=scc;
                num[scc]++;
            }
            while(v!=u);
        }
        return ;
    }
    void solve(int n){
        
        memset(dfn,0,sizeof(dfn));
        memset(inStack,false,sizeof(inStack));
        memset(num,0,sizeof(num));
        index=scc=top=0;
        for(int i=1;i<=n;i++){
        
            if(!dfn[i]){
        
                Tarjan(i);
            }
        }
        return ;
    }
    void init(){
        
        tot=0;
        memset(head,-1,sizeof(head));
        return ;
    }
    
    int main(){
        
        int t;
        scanf("%d",&t);
        int cas=1;
        while(t--){
        
            int n,m;
            scanf("%d%d",&n,&m);
            init();
            for(int i=0;i<m;i++){
        
                int a,b;
                scanf("%d%d",&a,&b);
                addedge(a,b);
            }
            solve(n);
            if(scc==1){
        
                printf("Case %d: -1\n",cas++);
                continue;
            }
            for(int i=1;i<=scc;i++){
        
                in[i]=0;
                out[i]=0;
            }
            for(int u=1;u<=n;u++){
        
                for(int i=head[u];i!=-1;i=edge[i].next){
        
                    int v=edge[i].to;
                    if(belong[u]==belong[v]){
        
                        continue;
                    }
                    out[belong[u]]++;
                    in[belong[v]]++;
                }
            }
            ll s=(ll)n*(n-1)-m;
            ll ans=0;
            for(int i=1;i<=scc;i++){
        
                if(in[i]==0||out[i]==0){
        
                    ans=max(ans,s-(ll)num[i]*(n-num[i]));
                }
            }
            printf("Case %d: %lld\n",cas++,ans);
        }
        return 0;
    }

[HDU 4635_Strongly connected_Tarjan]: http://acm.hdu.edu.cn/showproblem.php?pid=4635
[https_blog.csdn.net_u010372095_article_details_46888807]: https://blog.csdn.net/u010372095/article/details/46888807
[https_www.cnblogs.com_kuangbin_p_3230625.html]: https://www.cnblogs.com/kuangbin/p/3230625.html