UVA10765-Doves and bombs(BCC)

UVA10765-Doves and bombs(BCC)

大家好,又见面了,我是全栈君。

题意:给定一个n个点的连通的无向图。一个点的“鸽子值”定义为将它从图中删去后连通块的个数。

求“鸽子值”按降序排列的前m个。

思路:事实上题目就是要用来寻找割顶,我们仅仅需找出割顶。然后记录这个割顶属于几个不同连通分量的公共点,不是割点的,去掉之后。图的连通块数为1。

代码:

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

using namespace std;

const int MAXN = 10005;

struct node{
    int id, val;
}b[MAXN];

int n, m;
int pre[MAXN], low[MAXN], dfs_clock;
vector<int> g[MAXN];

void init() {
    for (int i = 0; i < n; i++) 
        g[i].clear();
    for (int i = 0; i < n; i++) {
        b[i].id = i; 
        b[i].val = 1;
    }     
}

bool cmp(node a, node b) {
    if (a.val == b.val)
        return a.id < b.id;
    return a.val > b.val;
}

int dfs(int u, int fa) {
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i]; 
        if (!pre[v]) {
            child++;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if (lowv >= pre[u]) {
                b[u].val++;
            }
        } 
        else if (pre[v] < pre[u] && v != fa) {
            lowu = min(lowu, pre[v]);
        }
    }
    if (fa < 0 && child == 1) b[u].val = 1;
    low[u] = lowu;
    return lowu;
}

void find_bcc(int n) {
    memset(pre, 0, sizeof(pre));
    memset(low, 0, sizeof(low));
    dfs_clock = 0;
    for (int i = 0; i < n; i++)
        if (!pre[i])
            dfs(i, -1);
}

int main() {
    while (scanf("%d%d", &n, &m)) {
        if (n == 0 && m == 0)
            break;
        init();
        int u, v;
        while (scanf("%d%d", &u, &v)) {
            if (u == -1 && v == -1)
                break;
            g[u].push_back(v);
            g[v].push_back(u); 
        }

        find_bcc(n);
        sort(b, b + n, cmp);
        for (int i = 0; i < m; i++)
            printf("%d %d\n", b[i].id, b[i].val);
        puts("");
    }     
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115689.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 微软的官方技术文档[通俗易懂]

    微软的官方技术文档[通俗易懂]https://docs.microsoft.com/zh-cn/dotnet/articles/csharp/language-reference/keywords/byte

  • qtablewidget设置滚动条样式_word滚动条作用

    qtablewidget设置滚动条样式_word滚动条作用IhaveaQTabWidgetwithtoomanytabsandtheyoverflowwithscrollerarrows.Iwanttoincreasethewidthofthescrollerarrowsbymorethantwiceofthedefaultwidthsotheyareeasiertouseona…

  • 风云私服架设教程_风云端游

    风云私服架设教程_风云端游需要软件:SQLsever2005pro本站提供下载将服务器端解压缩到D:盘D:\Sagasevr下有6个文件夹1:databaseSQL数据库文件夹2:LoginServer帐号登陆管理器3:WorldServer服务器数据管理器4:GameServer1游戏数据管理器4:GameServer2游戏数据管理器5:GameServer3游戏数据管理器6:GameS…

  • 2021年五面蚂蚁,java必背代码入门[通俗易懂]

    2021年五面蚂蚁,java必背代码入门[通俗易懂]一面(个人感觉回答得还不错)1.自我介绍2.说项目,项目问的非常深(本人提到之前做过的一篇关于FULLGC的问题定位和优化的项目以及一个多并发的项目)2.1对于自己产于过项目的系统定位是否清楚?2.2对于系统的各个模块是否清楚?2.3每个接口的tps?2.4对于上下游系统的依赖?2.5对于使用到的中间件、框架是否清楚?3.你觉得你做的项目中最有亮点的事情?4.memcacheredis同类中间的差异、优缺点?使用注意点有哪些?memcache可以存储的

  • MRT(MODIS Reprojection Tool) 下载及安装教程[通俗易懂]

    MRT(MODIS Reprojection Tool) 下载及安装教程[通俗易懂]大家下载MODIS数据的时候,大多是hdf的格式数据。HDF数据包括11个波段的数据(如下图),假如想要其中一个波段数据,我们需要批量提取,这时就要用到NASA提供的MODISReprojectionTool,此工具虽不能实现全自动的批量提取,但是可以实现按月进行数据的提取及拼接,官网提供了Linux、macos、windows的版本,本文以windows环境为例,说明MRT软件的安装。…

  • html5移动开发–js温馨提示

    html5移动开发–js温馨提示

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号