POJ3694 Network(Tarjan双联通分图 LCA 桥)_weixin_33929309的博客-程序员宝宝

链接:http://poj.org/problem?id=3694

题意:给定一个有向连通图,每次增加一条边,求剩下的桥的数量。

 

思路:

    给定一个无向连通图,添加一条u->v的边,求此边对图剩余的桥的数量的影响:

 若u,v在同一个边双联通分量中,则是否添加无影响。否则从u,vLCAu,v的边上所有的桥都不再是桥。

    在Tarjan算法中,对在同一个边双联通分量中的点使用并查集合并,实现缩点,同时记录父亲节点。若u,v属于不同的边双连通分量,将dfn较大的点(设为v)向上合并直到dfn[v] < dfn[u],再将u向上合并直到u = v。合并过程中,若发现桥则剩余桥的数量减1

 合并采用并查集,要在合并过程中对路径进行优化,否则超时。

 

 

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<algorithm>
const int INF = 0x3F3F3F3F;
using namespace std;
typedef long long LL;

const int N=100008,M=400008;
int head[N],tot,n,m,dfn[N],deep;
int bridge;
int fa[N], cnt[N], pre[N];
struct Node{
    int to,next;
}e[M];
void init(){
    memset(head, -1, sizeof(head));
    tot = 0;
    bridge = 0;
    for(int i = 1; i <= n; i++){
        fa[i] = i;
        cnt[i] = 1;
    }
}

int Find(int x){
    while(x != fa[x]){
        x = fa[x];
    }
    return x;
}
bool Union(int x, int y){
    int fx = Find(x);
    int fy = Find(y);
    if(fx!=fy){
    if(cnt[fx]>cnt[fy]){
            fa[fy]=fx;
            cnt[fx]+=cnt[fy];
        }else{
            fa[fx]=fy;
            cnt[fy]+=cnt[fx];
        }
        return true;
    }else{
        return false;
    }
}
inline void add(int u, int to){
    e[tot].to=to;
    e[tot].next=head[u];
    head[u]=tot++;
}
int dfs(int u, int fa){
    int lowu = dfn[u] = ++deep;//lowu为u及其后代所能到达的最远祖先
    for(int i=head[u];~i;i=e[i].next){
        int v = e[i].to;
        if(!dfn[v]){
    //树叶边,u到v且v未被访问
            pre[v] = u;
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if(lowv > dfn[u]){
                 bridge++;
            }else{
                Union(u, v);
            }
        }else if(dfn[v] < dfn[u] && v != fa){
            lowu = min(lowu, dfn[v]);//后向边
        }
    }
    return lowu;
}

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

int LCA(int u, int v){
    if(Find(u) == Find(v)){
        return bridge;
    }
    if(dfn[u] > dfn[v]){
        swap(u, v);
    }
    while(dfn[u] < dfn[v]){
        if(Union(v, pre[v])){
            bridge--;
        }
        v = pre[v];
    }
    while(u != v){
        if(Union(u, pre[u])){
            bridge--;
        }
        u = pre[u];
    }
    return bridge;
}

int main(){
    int t = 0;
    while(~scanf("%d %d", &n, &m) && (n || m)){
        init();
        int a, b, q;
        while(m--){
            scanf("%d %d", &a, &b);
            add(a, b);
            add(b, a);
        }
        tarjan();
        scanf("%d", &q);
        printf("Case %d:\n",++t);
        while(q--){
            scanf("%d %d", &a, &b);
            printf("%d\n", LCA(a, b));
        }
        printf("\n");
    }
    return 0;
}

 

 

 

转载于:https://www.cnblogs.com/IMGavin/p/5537644.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_33929309/article/details/93788538

智能推荐

视频录制小结_weixin_30458043的博客-程序员宝宝

1.解决视频录制前后画面缩放问题就是把下面的两个参数设置成一样的,具体设置成多少要看需求 &lt;1&gt;.parmeters.setPreviewSize(640, 480); &lt;2&gt;.mediaRecorder.setVideoSize(640, 480);2.视频是展示在SurfaceView上面的,所以视频录制画面的大小,缩放情况和SurfaceView布局是密切...

LeeCode(No2 - Add Two Numbers)_weixin_30299539的博客-程序员宝宝

LeeCode是一个有意思的编程网站,主要考察程序员的算法第二题:You are given twonon-emptylinked lists representing two non-negative integers. The digits are stored inreverse orderand each of their nodes contain a sing...

org.springframework.web.util.NestedServletException: Request processing failed; nested exception is ..._weixin_30257433的博客-程序员宝宝

之前做的项目是resteasy的上传,代码没有问题,断点都不进来呢。我以为可以直接移植到SpringMVC,但是SpringMVC不支持MultipartFormDataInput ,用MultipartFile就可以了。老的无法兼容新的。正确代码如下@RequestMapping(value = "/importExcelForEduQuestion",produces = ...

Web_PHP_Curl浅说;_cyb_23的博客-程序员宝宝

<?php/** * curl会话 * @author 2WR3_cyb */class CurlClass { /** * Curl使用示例 * @param string $url 请求路径,如'http://x.x.x'; * @param array $fields 请求参数,如array('var' => 'value'), or can

黑马程序员--面对对象3_捌年的博客-程序员宝宝

------- android培训、java培训、期待与您交流! ----------一、继承定义:  在定义和实现一个类的时候,可以在一个已经存在的类的基础之上来进行,把这个已经存在的类所定义的内容作为自己的内容,并可以加入若干新的内容,或修改原来的方法使之更适合特殊的需要,这就是继承。继承是子类自动共享父类数据和方法的机制,这是类之间的一种关系,提高了软件的可重用性和可

随便推点

判断listview滚动到最顶部最底部_weixin_30480075的博客-程序员宝宝

下面的方法在ListView外面能用, 自定义ListView里面不能用. privateOnScrollListenermyListener=newOnScrollListener(){publicvoidonScrollStateChanged(AbsListViewview,intscrollState){switch(...

Hello world !_weixin_30340617的博客-程序员宝宝

今天开通了博客看Python的视频里老师说从开始就要养成写bolg和github的习惯他说他当时去汽车之家就没带简历~ 哈哈 光是博客就收了他那我今年大三了对编程能力还不是很强。学的智能科学与技术。之后每次做完一个小作业 都会记录再博客上,渐渐的发现我也可以做一名有趣的程序员让编程改变世界 ! keep up !BTW I'm a poper ... c...

Redis工具类最全_绿帽大牛的博客-程序员宝宝_redis工具包

package com.slzy.biz.common.util.redis;import java.util.List;import java.util.Map;import java.util.Set;import java.util.concurrent.TimeUnit;import com.slzy.biz.common.util.redis.justin.CachetValueAbstract;import org.springframework.beans.factory.an.

RS232与串口通信的4个注意事项详解_杭州飞畅的博客-程序员宝宝_rs232奇偶校验

RS232和串口通信,用于串口设备的数据采集软件,包括仪表、天平、秤或任何RS232仪器。WinWedge直接将数据捕获到Excel、Access或任何Windows应用程序或网页。它甚至可以从COM端口发送命令,因此您可以通过热键,按钮或DDE控制您的设备。许多PC和兼容计算机都配有两个串行端口和一个并行端口。虽然这两种类型的端口用于与外部设备通信,但它们以不同的方式工作。并行端口通过8条单独的线路一次发送和接收8位数据。这样可以非常快速地传输数据。然而,由于必须包含单根电线的数量,所需的电缆更笨

spring cloud项目mybatis集成Hbase/MySql多数据源_木鱼&金鱼的博客-程序员宝宝_mybatis整合hbase

公司最近的项目需要在spring cloud 上集成Hbase和mysql,连接Hbase使用Phoenix来连接先来看看项目结构:核心pom依赖如下,其中 phoenix-4.7.0.2.5.3.0-37-client.jar使用的是本地的jar包其他spring sloud所需依赖自行添加即可 &lt;dependency&gt; &...

推荐文章

热门文章

相关标签