C++[Tarjan求点双连通分量,割点][HNOI2012]矿场搭建
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++[Tarjan求点双连通分量,割点][HNOI2012]矿场搭建,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2656字,纯文字阅读大概需要4分钟。
内容图文
最近在学图论相关的内容,阅读这篇博客的前提是你已经基本了解了Tarjan求点双。
由割点的定义(删去这个点就可使这个图不连通)我们可以知道,坍塌的挖煤点只有在割点上才会使这个图不连通,而除了割点的其他点上则无可厚非,所以我们只需要考虑这个图的割点的情况。
那么我们就可以求出所有的点双连通分量, 如果这个点双仅有一个割点,那么这个割点坍塌后这个点双就被“孤立”了,所以需要在这个点双里设置一个救援出口。
那么这个点双如果包含多个割点呢?假设它的其中一个割点坍塌了,它还可以从另外几个割点出去。
所以我们只需要判断有几个点双只有一个割点,便是我们要设置的救援出口的数量。
有的同学可能要问了,如果所有点双都有多个割点呢?这种情况是不存在的,因为如果这样所有点双都变得联通了,也就不存在点双了。
关于方案的总数,只需要运用乘法原理。需要注意的是如果整个图就是一个点双,那么救援出口应该是两个,方案数是节点数\(n\),\(n*(n-1)/2\)。
代码
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <cstdio>
using namespace std;
#define N 510
#define LL long long
LL vis[N],ans1,ans2=1,bcc[N],n,m,num,cntd,DFN[N],IsCut[N],low[N],belong[N];
vector <LL> G[N];
vector <LL> vecd[N];
struct edge {
int u,v;
edge() {};
edge(int U,int V) {u=U;v=V;}
};
stack <edge> st;
LL read() {
LL f=1,s=0;char a=getchar();
while(!(a>='0'&&a<='9')) { if(a=='-') f=-1 ; a=getchar(); }
while(a>='0'&&a<='9') { s=s*10+a-'0'; a=getchar();}
return f*s;
}
void init() {
memset(bcc,0,sizeof(bcc));
memset(DFN,0,sizeof(DFN));
memset(vis,0,sizeof(vis));
memset(IsCut,0,sizeof(IsCut));
memset(belong,0,sizeof(belong));
memset(low,0,sizeof(low));
for(int i=1;i<=N;i++) G[i].clear(),vecd[i].clear();
for(LL i=1,u,v;i<=m;i++) {
u=read();v=read();
vis[u]=vis[v]=1;
G[u].push_back(v);
G[v].push_back(u);
}
ans1=cntd=0;
ans2=1;
}
void Tarjan(LL u,LL fa) {
LL child=0;
DFN[u]=low[u]=++num;
for(LL i=0;i<G[u].size();i++) {
LL v=G[u][i];
if(!DFN[v]) {
child++;
st.push( edge(u,v) );
Tarjan(v,u);
if(low[v]>=DFN[u]) {
IsCut[u]=1;
cntd++;
for(;;) {
edge x=st.top();st.pop();
if(belong[x.u] != cntd) {vecd[cntd].push_back(x.u); belong[x.u] = cntd;}
if(belong[x.v] != cntd) {vecd[cntd].push_back(x.v); belong[x.v] = cntd;}
if(x.u == u && x.v == v) break;
}
}
low[u]=min(low[u],low[v]);
}
else if(DFN[u]>DFN[v] && v!=fa)
low[u]=min(low[u],DFN[v]);
}
if(fa<0 && child==1)
IsCut[u]=0;
}
int main() {
int flag=0;
while(cin>>m && m) {
init();
flag++;
for(int i=1;vis[i];i++)
if(!DFN[i])
Tarjan(i,-1);
for(LL i=1;i<=cntd;i++) {
for(int j=0;j<vecd[i].size();j++)
if(IsCut[vecd[i][j]]) bcc[i]++;//bcc统计第i个点双的割点数量
if(bcc[i]==1){ //仅有一个割点,统计答案
ans1++;
ans2*=(vecd[i].size()-1);//乘法原理
}
}
LL siz=vecd[1].size();
if(!ans1) cout<<"Case "<<flag<<": "<<"2"<<' '<<siz*(siz-1)/2<<endl;//特判原图是不是点双
else cout<<"Case "<<flag<<": "<<ans1<<' '<<ans2<<endl;
}
}
内容总结
以上是互联网集市为您收集整理的C++[Tarjan求点双连通分量,割点][HNOI2012]矿场搭建全部内容,希望文章能够帮你解决C++[Tarjan求点双连通分量,割点][HNOI2012]矿场搭建所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。