acwing-396. 矿场搭建(Tarjan点双连通分量)「建议收藏」

acwing-396. 矿场搭建(Tarjan点双连通分量)「建议收藏」煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。输入格式输入文件有若干组数据,每组数据的第一行是一个正整数 N,表示工地的隧道数。接下来的 N 行每行是用空格隔开的两个整数 S 和 T,表示挖煤点 S 与挖煤点 T 由隧道直接连

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。

为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。

于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。

输入格式
输入文件有若干组数据,每组数据的第一行是一个正整数 N,表示工地的隧道数。

接下来的 N 行每行是用空格隔开的两个整数 S 和 T,表示挖煤点 S 与挖煤点 T 由隧道直接连接。

注意,每组数据的挖煤点的编号为 1∼Max,其中 Max 表示由隧道连接的挖煤点中,编号最大的挖煤点的编号,可能存在没有被隧道连接的挖煤点。

输入数据以 0 结尾。

输出格式
每组数据输出结果占一行。

其中第 i 行以 Case i: 开始(注意大小写,Case 与 i 之间有空格,i 与 : 之间无空格,: 之后有空格)。

其后是用空格隔开的两个正整数,第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口,第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 264,输出格式参照以下输入输出样例。

数据范围
1≤N≤500,
1≤Max≤1000

输入样例:
9
1  3
4  1
3  5
1  2
2  6
1  5
6  3
1  6
3  2
6
1  2
1  3
2  4
2  5
3  6
3  7
0
输出样例:
Case 1: 2 4
Case 2: 4 1
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = 1e3 + 10;
typedef unsigned long long ULL;
struct Edge{ 
   
    int v,next;
}edge[M];
int head[N],cnt;
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
int in[N];
int sccno;
vector<int>g[N];
int low[N],num[N],dfn;
int sta[N],top;
int is_solate[N],cut[N];
//点双连通分量
void Tarjan(int u,int fa){ 
   
    num[u] = low[u] =  ++dfn;
    if(fa == -1 && head[u] == -1){ 
         //孤立节点特判
        sccno ++;
        g[sccno].push_back(u);
        is_solate[sccno] = true;
        return;
    }
    sta[top ++] = u;
    int child = 0;
    for(int i = head[u];~i;i = edge[i].next){ 
   
        int v = edge[i].v;
        if(v == fa)continue;
        if(!num[v]){ 
   
            child ++;
            Tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] >= num[u]){ 
   
                if(fa != -1)cut[u] = true;
                int t;
                sccno ++;
                while(true){ 
   
                    t = sta[-- top];
                    g[sccno].push_back(t);
                    if(t == v)break;
                }
                g[sccno].push_back(u);
            }
        }
        else low[u] = min(low[u],num[v]);
    }
    if(fa == -1 && child >= 2)cut[u] = true;
}
int main(){ 
   
    int m = 0;
    int x,y;
    int n;
    int T = 0;
    while(cin>>m,m){ 
   
        n = 0;
        memset(head,-1,sizeof head);
        memset(num,0,sizeof num);
        memset(low,0,sizeof low);
        memset(cut,0,sizeof cut);
        dfn = 0,cnt = 0;
        for(int i = 1;i <= sccno;i ++)g[i].clear();
        sccno = 0;
        for(int i = 0;i < m;i ++){ 
   
            cin>>x>>y;
            add(x,y),add(y,x);
            n = max(n,max(x,y));
        }
        for(int i = 1;i <= n;i ++){ 
   
            if(!num[i])Tarjan(i,-1);
        }
        ULL res = 0;
        ULL c = 1;
        for(int i = 1;i <= sccno;i ++){ 
   
            int d = 0;
            for(auto &a : g[i]){ 
   
                if(cut[a])d ++;
            }
            int a = g[i].size() - d;
            if(d == 0){ 
   
                if(a == 1)res += 1;
                else res += 2,c *= (a * (a - 1) / 2);
            }
            else if(d == 1){ 
   
                if(a == 1)res += 1;
                else res += 1,c *= a;
            }
        }
        printf("Case %lld: %lld %lld\n",++T,res,c);
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • 汇编指令和机器码的对应表_汇编和机器码对照表

    汇编指令和机器码的对应表_汇编和机器码对照表指令集依照机器操作码、汇编助记符和汇编操作数来描述指令,遵循下列约定:lreg8:8位寄存器。lreg16:16位寄存器。lmem8:8位内存数值。lmem16:16位内存数值。limmed8:8位立即数值。limmed16:16位立即数值。limmed32:32位立即数值。lsegReg:16位段寄存器。机器操作码汇编助记符和操作数00ADDreg8/mem8,reg801ADD

  • 怎么新建pytest的ini文件_qt读写配置文件

    怎么新建pytest的ini文件_qt读写配置文件前言pytest配置文件可以改变pytest的运行方式,它是一个固定的文件pytest.ini文件,读取配置信息,按指定的方式去运行查看pytest.ini的配置选项pytest-h找到以下

  • C/S结构与B/S结构的区别_C/s架构是什么意思

    C/S结构与B/S结构的区别_C/s架构是什么意思深入理解B/S与C/S架构阅读目录: 什么是C/S架构 什么是B/S架构 B/S架构的几种形式 发展前景 一、什么是C/S架构C/S架构是第一种比较早的软件架构,主要用于局域网内。也叫客户机/服务器模式。它可以分为客户机和服务器两层:第一层:在客户机系统上结合了界面显示与业务逻辑;第二层:通过网络结合了数据库服务器。…

  • Git入门级常用命令(1)

    Git入门级常用命令(1)

  • Activiti 简易教程「建议收藏」

    Activiti 简易教程「建议收藏」一搭建环境1.1  JDK6+activiti运行在版本6以上的JDK上。转到OracleJavaSE下载页面,点击按钮“下载JDK”。网页中也有安装说明。要核实安装是否成功,在命令行上运行java–version。将打印出安装的JDK的版本。1.2  Ant1.8.1+从Ant[http://ant.apache.org/bindownload.c

  • 计算机网络 — HTTP协议 和 HTTPS[通俗易懂]

    计算机网络 — HTTP协议 和 HTTPS[通俗易懂]1.了解HTTP协议1.1HTTP是什么HTTP(HyperTextTransferProtocol,超文本传输协议)是一种应用非常广泛的应用层协议.所谓“超文本”的含义,就是传输的内容不仅仅是文本(比如html,css这个就是文本),还可以是一些其他的资源,比如图片,视频,音频等二进制的数据1.2抓包工具的使用1.Fiddler的下载①可以直接在官网下载Fiddler官网地址②也可以直接进入fiddler搜索页2.Fiddl

    2022年10月16日

发表回复

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

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