危险系数 蓝桥杯 求两点间割点 tarjan && poj 1523

题面

问题描述
抗日战争时期，冀中平原的地道战曾发挥重要作用。地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。我们来定义一个危险系数DF(x,y)：对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。本题的任务是：已知网络结构，求两站点之间的危险系数。输入格式
输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数，通道数；接下来m行，每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条通道；最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。输出格式
一个整数，如果询问的两点不连通则输出-1.
样例输入
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
样例输出
2

分析

求两点之间的割点

于是我就去学了一下tarjan算法

推荐几篇博客：
http://keyblog.cn/article-80.html
https://www.cnblogs.com/mxrmxr/p/9715579.html

学了tarjan算法之后去做了一下POJ 1523（割点模板题）

题目链接

题意：

给一个无向图，求出所有割点以及去电每个割点后整个图连通分量增加的个数

直接上代码好了：

/*POJ 1523 SPF 求割点和每个割点去掉后增加的连通分量的个数 
Run ID	   User	   Problem	Result	  Memory	Time	Language  Code Length	Submit Time
21061713   apare   1523	    Accepted  164K	    0MS	    C++	1     476B	        2019-11-17 09:41:21
*/
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1000+50;
const int maxm = 1000000+100;
int head[maxn],tot,cnt;
struct Node{int to,Next;
}node[maxm*2];
int dfn[maxn],low[maxn];
void init()
{tot = 0,cnt=0;memset(dfn,0,sizeof(dfn));memset(head,-1,sizeof(head));
}
void addedge(int from,int to)
{node[tot].to = to;node[tot].Next = head[from];head[from] = tot++;
} 
int ca;                        
map<int,int> mp;
map<int,int>::iterator it;
void tarjan(int x,int root,int fa)
{dfn[x] = low[x] = ++cnt;int child = 0;for(int i=head[x];i!=-1;i=node[i].Next){int to = node[i].to;if(!dfn[to]) //这个节点to还没被访问过 {++child;tarjan(to,root,x);low[x] = min(low[x],low[to]);if(x!=root&&dfn[x]<=low[to]) ++mp[x]; }else if(to!=fa) //这个节点已经被访问过了,而且不是父节点 {low[x] = min(low[x],dfn[to]);} }if(x==root&&child>=2) mp[x] = child-1;
}
void solve()
{mp.clear();memset(dfn,0,sizeof(dfn));tarjan(1,1,1);printf("Network #%d\n",++ca);if(!mp.size()){ printf("  No SPF nodes\n\n");return;}for(it=mp.begin();it!=mp.end();++it)                   printf("  SPF node %d leaves %d subnets\n",it->first,it->second+1);printf("\n"); 
}
int main()
{int u,v=10;init();while(scanf("%d",&u)!=EOF){if(u==0){if(v==0) break;solve();init();}else{scanf("%d",&v);addedge(u,v);addedge(v,u);		}	v = u;}return 0;
}

会了tarjan算法以后我们再来看危险系数这道题

题意：求无向图中给定两点之间的割点数

ps：参考了网上几乎所有博客，大多位dfs暴力枚举或者暴力并查集
  主要参考这篇文章

思路：

• 先找出图的所有割点，然后分别判断是否满足为两点st,ed的割点
• 一个点是两点间的割点要满足几个条件：

1. 该点可达ed
2. 至少一个子节点可达ed回不去更早的节点

代码：

/*
危险系数 xzc
给定一个图，求两个点之间割点的个数 
许智超	危险系数	11-18 17:16	1.665KB	C++	正确	100	0ms	16.23MB
*/
#include 
using namespace std;
const int maxn = 1000+50;
const int maxm = 2000000+50;
int head[maxn],tot,st,ed;
int cnt,dfn[maxn],low[maxn];
bool reachEd[maxn];
set<int> ans;
set<int>::iterator it;
struct Node{int to,Next;
}node[maxm];
void initEdge()
{tot = 0;memset(head,-1,sizeof(head));
}
void addedge(int from,int to)
{node[tot].to = to;node[tot].Next = head[from];head[from] = tot++;
}
void init()
{cnt = 0;memset(dfn,0,sizeof(dfn));memset(reachEd,false,sizeof(reachEd));ans.clear();
}
void tarjan(int x,int root,int fa_x)
{dfn[x] = low[x] = ++cnt;int child = 0;for(int i=head[x];i!=-1;i=node[i].Next){int to = node[i].to;if(!dfn[to]){++child;tarjan(to,root,x);low[x] = min(low[x],low[to]);if(to==ed||reachEd[to]) reachEd[x] = true;if(x==root&&child>=2) ans.insert(x);if(x!=root&&low[to]>=dfn[x]) ans.insert(x);}else if(to!=fa_x){low[x] = min(low[x],dfn[to]);}}
}
int main()
{	int m,n,u,v,ca=0;while(cin>>n>>m){initEdge();for(int i=0;i<m;++i){scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}scanf("%d%d",&st,&ed);if(ca++){init();}tarjan(st,st,st);reachEd[ed] = true;int res = 0;for(it=ans.begin();it!=ans.end();++it){int x = *it;if(x==ed||x==st||!reachEd[x]) continue; //起点和终点都不算两点之间的割点 int add = 0;for(int i=head[x];i!=-1;i=node[i].Next){int to = node[i].to;if(low[to]>=dfn[x]&&reachEd[to]){add = 1;break;}}res += add;}printf("%d\n",res);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！