历届试题危险系数（dfs求割点）

野性酷女 2022-06-18 02:41 193阅读 0赞

问题描述

抗日战争时期，冀中平原的地道战曾发挥重要作用。

地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。

我们来定义一个危险系数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

样例输出

题解：显然是两点之间求割点的个数。直接dfs起始点到终点的路径数ans，以及通过每个点的次数times。如果ans=times，那么这个点就是割点。最后还要减去首尾两点。

代码：

//package Main;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class Main {
    
    	static int mp[][]=new int[2010][2010];
    	static int vis[]=new int[2010];
    	static int node[]= new int [2010];
    	static int ans=0;
    	static int count =0 ;
    	static int k2=0,n=0;
    	static int times[]=new int [2010];
    	public static void main(String[] args) {
    		/*
    		LinkedList<Integer> que = new LinkedList<Integer>();
    		for(int  i=1;i<=10;i++){
    			que.add(i);
    		}
    		while(!que.isEmpty())
    		{
    			que.pop();
    			//System.out.println(que.pop());
    		}
    		System.out.println("finish");
    		*/
            Scanner cin=new Scanner(System.in);
             n=cin.nextInt();
            int m=cin.nextInt();
            for(int i=1;i<=m;i++)
            {
            	int u=cin.nextInt();
            	int v=cin.nextInt();
            	mp[u][v]=1;
            	mp[v][u]=1;
            }
            int k1=cin.nextInt();
             k2=cin.nextInt();
            vis[k1]=1;
            node[0]=k1;
            dfs(k1,1);
            if(ans==0)
            {
            	System.out.println("0");
            }
            else
            {
            	for(int i=1;i<=n;i++)
                {
                	if(times[i]==ans)
                	{
                		count++;
                	}
                }
                System.out.println(count-2);
            }
            
    	}
    	static void dfs(int e,int step)
    	{
    		if(e==k2)  
    	    {  
    	       ans++;  
    	       for(int i=0;i<step;i++)  
    	        {  
    	            times[node[i]]++;  
    	          
    	        }
    	    }  
    	    else  
    	    {  
    	        for(int i=1;i<=n;i++)  
    	        {  
    	            if(vis[i]==0 && mp[e][i]==1)  
    	            {  
    	                vis[i]=1;  
    	                node[step]=i;  
    	                dfs(i,step+1);  
    	                vis[i]=0;  
    	            }  
    	        }  
    	    }  
    	}
    
    }

也写一个C++的...

#include<bits/stdc++.h>
    using namespace std;
    
    int mp[2005][2005];
    int times[2005];
    int node[2005];
    int vis[2005];
    int k2;
    int ans;
    int n,m;
    void dfs(int k1,int step)
    {
    	if(k1==k2)
    	{
    	   ans++;
    	   for(int i=0;i<step;i++)
    		{
    			times[node[i]]++;
    			//cout<<"times[node[i]]="<<times[node[i]]<<endl;
    		//	cout<<"ans="<<ans<<endl;
    		//return;
    			
    		}
    	//	for(int i=0;i<step;i++) cout<<node[i]<<" ";
    	//	cout<<endl;
    	}
    	else
    	{
    		for(int i=1;i<=n;i++)
    		{
    			if(vis[i]==0 && mp[k1][i]==1)
    			{
    				vis[i]=1;
    				node[step]=i;
    				dfs(i,step+1);
    				vis[i]=0;
    			}
    		}
    	}
    	
    }
    int main()
    {
    	//freopen("in.txt","r",stdin);
    	int k1;
    	memset(vis,0,sizeof(vis));
    	memset(node,0,sizeof(node));
    	memset(times,0,sizeof(times));
    	cin>>n>>m;
    	for(int i=0;i<m;i++)
    	{
    		int u,v;
    		cin>>u>>v;
    		mp[u][v]=1;
    		mp[v][u]=1;	
    	}	
    	cin>>k1>>k2;
    	node[0]=k1;
    	vis[k1]=1;
    	dfs(k1,1);
    	if(ans==0){
    		return 0*printf("-1");
    	}
    	int count=0;
    	for(int i=1;i<=n;i++){
    		if(times[i]==ans){
    			count++;
    		}
    	}
    	cout<<count-2<<endl;
    	return 0;
    }