危险系数 蓝桥杯 求两点间割点 tarjan && poj 1523 SPF Apare_xzc
危险系数 蓝桥杯 求两点间割点 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 <iostream>
#include <cstdio>
#include <map>
#include <cstring>
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的割点
- 一个点是两点间的割点要满足几个条件：
- 该点可达ed
- 至少一个子节点可达ed回不去更早的节点
代码：
/* 危险系数 xzc 给定一个图，求两个点之间割点的个数 许智超 危险系数 11-18 17:16 1.665KB C++ 正确 100 0ms 16.23MB */
#include <bits/stdc++.h>
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;
}
