您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

HDU 4635 Strongly connected

卞振伟2019-09-25【ACM||算法】人已围观

简介题意:
题目明显告诉了这是强连通的题,询问最多添加多少条边,结果得到的依旧不是强连通图,
如果一开始就是强连通图,则输出“-1”。
思路:
首先,特判的肯定先解决,依旧是tarjan算法,如果是一个强连通图,输出“-1”。然后因为
该题是求最大,而且是连通图和非连通图的临界条件。于是可以yy一下最大值的情况是怎样的。
因为还是tarjan然后求DAG,这是最基本的,即我们已经将原图变成DAG了,此时还不能是强连通图,
则必须有一个DAG对于其他

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

const int maxn = 1e5+7;
const int inf = 0x3f3f3f3f;

vector<int> G[maxn];
stack<int> s;
int dfn[maxn], low[maxn], vst[maxn], belong[maxn], num[maxn];
int in[maxn],out[maxn];
int n, m, tot, cnt, msum;
void Tarjan(int x){
    dfn[x] = low[x] = ++tot;
    s.push(x);
    vst[x] = 1;
    for (int i = 0; i < G[x].size();i++){
        int v = G[x][i];
        if(!dfn[v]){
            Tarjan(v);
            low[x] = min(low[x], low[v]);
        }
        else if(vst[v]){
            low[x] = min(low[x], dfn[v]);
        }
    }
    if(dfn[x] == low[x]){
        cnt++;
        while (1){
            int now = s.top();
            s.pop();
            vst[now] = 0;
            num[cnt]++;
            belong[now] = cnt;
            if(now==x) break;
        }
    }
}

void init(){
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(vst, 0, sizeof(vst));
    memset(belong, 0, sizeof(belong));
    memset(num, 0, sizeof(num));
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    for(int i = 1;i <= n; ++i)
        G[i].clear();
}

int main(){
    int t;
    int k = 1;
    scanf("%d",&t);
    while (t--){
        init();
        scanf("%d %d", &n, &m);
        for (int i = 0;i < m; ++i){
            int x, y;
            scanf("%d %d", &x, &y);
            G[x].push_back(y);
        }
        tot = 0, cnt = 0;
        for (int i = 1;i <= n; ++i){
            if(!dfn[i])
                Tarjan(i);
        }

        if(cnt == 1){
            printf("Case %d: -1\n", k++);
            continue;
        }

        for(int i = 1; i <= n; ++i) {
            for(int j = 0; j < G[i].size(); ++j) {
                int u = belong[i];
                int v = belong[ G[i][j] ];
                if(u != v){
                    out[u] ++;
                    in[v] ++;
                }
            }
        }
        msum = inf;
        for (int i = 1;i <= cnt; ++i){
            if(!out[i])
                msum = min(msum, num[i]);
            if(!in[i])
                msum = min(msum, num[i]);
        }
        ll ans = (long long) n * (n - 1);// 完全图的边数(n*(n-1))
        // 这个特殊的DAG与外界不能相连的边数,即该DAG里的顶点个数乘以除该DAG的顶点外的所有顶点数
        ans -= (long long) msum * (n - msum);
        printf("Case %d: %d\n", k++, ans - m);// 原来图本就存在的边数m
    }
    return 0;
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:242篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00