【并查集】蓝桥杯原题:危险系数 - 木东驿站 - Powered by MoodBlog

CONTENT

【并查集】蓝桥杯原题:危险系数

题目描述

问题描述 
抗日战争时期,冀中平原的地道战曾发挥重要作用。 
地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。 
我们来定义一个危险系数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

JAVA代码如下:

import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int n=scanner.nextInt(),m=scanner.nextInt();
		BFsets bf = new BFsets(n);
		for(int i=0;i<n;i++){
			bf.addset(i);
		}
		int[][] data = new int[m][2];
		for(int i=0;i<m;i++){
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			data[i][0] = a;
			data[i][1] = b;
		}
		bf.data = data;
		bf.start = scanner.nextInt();
		bf.end = scanner.nextInt();
		
		if(bf.start()==false){
			System.out.println(-1);
		}else{
			System.out.println(bf.res);
		}
		scanner.close();
	}
}
class BFset{
    public int data;
    public int parent;
}
class BFsets{
    private BFset[] bfset;
    private int n=0;
    public int[][] data;
    public int res = 0;
    public int start;
    public int end;
    BFsets(int n){
        bfset = new BFset[n+1];//预留n位置
        this.n = n;
    }
    void addset(int n){
        bfset[n] = new BFset();
        bfset[n].data = n;
        bfset[n].parent = n;
    }
    //初始化 n为去掉的点
    void ini(int nn){
    	for(int i=0;i<n;i++){
            bfset[i].data = i;
            bfset[i].parent = i; 		
    	}
    	for(int i=0;i<data.length;i++){
    		if(data[i][0]!=nn&&data[i][1]!=nn){
    			unionSets(data[i][0]-1,data[i][1]-1);
    		}
    	}
    }
    //查询元素所在的集合
    int findSet(int n){
        if(bfset[n].parent==n){
            return n;
        }else{
            return findSet(bfset[n].parent);
        }
    }
    //两个元素所在集合合并
    void unionSets(int a,int b){
        a = findSet(a);
        b = findSet(b);
        if(bfset[a].data>bfset[b].data){
            bfset[b].parent = a;
        }else{
            bfset[a].parent = b;
        }
    }
    //判断两个元素是否属于同一个集合
    boolean issame(int a,int b){
        if(findSet(a)==findSet(b)){
            return true;
        }else{
            return false;
        }
    }
    public boolean start(){
    	ini(-1);
    	if(issame(start-1,end-1)!=true){
    		return false;
    	}
    	for(int i=0;i<n;i++){
    		if(i!=start-1&&i!=end-1){
        		ini(i+1);
        		if(issame(start-1,end-1)!=true){
        			res++;
        		}		
        	}
    	}
    	return true;
    }
}


个快快 2017年11月13日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号