抗日战争时期,冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。
我们来定义一个危险系数 DF(x,y):
对于两个站点?x?和 y(x!=y),?如果能找到一个站点?z,当?z?被敌人破坏后,x?和?y?不连通,那么我们称?z?为关于?x,y?的关键点。相应的,对于任意一对站点?x?和?y,危险系数 DF(x,y)?就表示为这两点之间的关键点个数。
本题的任务是:已知网络结构,求两站点之间的危险系数。
这题可以用dfs来解,具体看代码
#include <bits/stdc++.h>
using namespace std;
int n,m,u,v,ans,cnt[1010],sum;
bool b[1010],a[1010][1010];
void dfs(int N);
int main()
{
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d",&u,&v);
a[u][v]=a[v][u]=1;//无向,令u到v和v到u为1
}
scanf("%d%d",&u,&v);
dfs(u);
if(sum>0)
{
for(int i=1;i<=n;i++)
if(cnt[i]==sum) //如果这个点被走过的总次数与路径总数相等(必经点)
ans++; //那么删去这个点起点与终点间一定不连通。
printf("%d",ans-1); //因为终点也被算在内,所以总危险系数要减去起点的1。
}
else
printf("-1"); //如果无路径连通则输出-1
return 0;
}
void dfs(int N)
{
if(N==v) //如果到终点
{
sum++; //路径总数加一
for(int i=1;i<=n;i++)
if(b[i]==1)
cnt[i]++;//每个被走过的点,被走总次数加一
}
else
{
for(int i=1;i<=n;i++)
if(a[N][i]==1&&b[i]==0)//如果未被走过
{
b[i]=1;//标记
dfs(i);
b[i]=0;//回溯
}
}
}