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)


相关推荐

  • js字符串截取为数组

    js字符串截取为数组varstr=”hello,word,java,eclipse,jsp”;//字符串截取为数组varstrArr=str.split(“,”);for(j=0,len=strArr.length;j<len;j++){alert(strArr[j]);};

  • 高通MSM8953 LK阶段配置使用I2C8[通俗易懂]

    高通MSM8953 LK阶段配置使用I2C8[通俗易懂]项目场景: 因为项目需要,需要在高通MSM8953平台的LK阶段使用I2C8设备。但是MSM8953平台LK阶段并没有配置好I2C8接口,因此调试I2C8成为当务之急。本文只介绍在LK阶段配置使用I2C5的方法。调试需要:1、文档:BAMLow-SpeedPeripherals(BLSP)UserGuide查看文档,有I2C介绍如下:I2c3对应的物理地址为0x78B7000,中断IRQ:97,时钟信号clk:clk_gcc_blsp1_qup3_i2c_apps_clk

    2022年10月19日
  • 新硬盘如何初始化_linux系统初始化命令

    新硬盘如何初始化_linux系统初始化命令在物理机或者云服务器新加了一块磁盘,为了让Linux系统能够正常使用这块磁盘,要先对磁盘进行一些初始化工作。命令先了解一下我们要使用到的Linux命名:df:用于显示目前Linux系统上的文件系统的磁盘使用情况统计fdisk:用于管理磁盘分区表mount:用于挂载Linux系统外的文件partprobe:用于重读分区表,当出现删除文件后,出现仍然占用空间。可以在不重启的情况下重读分…

  • findIndex()方法[通俗易懂]

    findIndex()方法[通俗易懂]findIndex()方法返回数组中通过测试的第一个元素的索引(作为函数提供)。findIndex()方法对数组中存在的每个元素执行一次函数:如果找到函数返回true值的数组元素,则findIndex()返回该数组元素的索引(并且不检查剩余值)否则返回-1注释:findIndex()不会为没有值的数组元素执行函数。注释:findIndex()不会改变原始数组。获取数组中第一个值等于或大于18的元素的索引:varages=[3,10,18,20];funct

    2022年10月26日
  • 面向对象设计大作业——火车售票系统

    面向对象设计大作业——火车售票系统

发表回复

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

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