05 File Transfer（java实现）

File Transfer (25分)

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

Input Specification:

Each input file contains one test case. For each test case, the first line contains N (2≤N≤10
​4
​​ ), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:

I c1 c2
where I stands for inputting a connection between c1 and c2; or

C c1 c2
where C stands for checking if it is possible to transfer files between c1 and c2; or

S
where S stands for stopping this case.

Output Specification:

For each C case, print in one line the word “yes” or “no” if it is possible or impossible to transfer files between c1 and c2, respectively. At the end of each case, print in one line “The network is connected.” if there is a path between any pair of computers; or “There are k components.” where k is the number of connected components in this network.

Sample Input 1:

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S

Sample Output 1:

no
no
yes
There are 2 components.

Sample Input 2:

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
I 1 3
C 1 5
S

Sample Output 2:

no
no
yes
yes
The network is connected.

解题思路

使用并查集进行集合连接与查找
1、初始化集合，令每个节点为自己的根节点，即s[]函数值为-1，表示根节点
2、读取指令，进行操作：
每种指令对应不同操作：I表示连接； C表示判断是否连接；S表示输出所有点是否全部连接

import java.util.*;

public class  FileTransferDemo
{
	public static void main(String[] args) 
	{
		/**
			使用并查集进行集合连接与查找
			1、初始化集合，令每个节点为自己的根节点，即s[]函数值为-1，表示根节点
			2、读取指令，进行操作：
				每种指令对应不同操作：I表示连接； C表示判断是否连接；S表示输出所有点是否全部连接
		*/
		Scanner scan = new Scanner(System.in);
		String ns = scan.nextLine();
		int n = Integer.parseInt(ns);		//集合中的元素数
		int[] s = new int[n+1];

	//1、初始化集合
		gather(s, n);
	//2、读取指令，进行操作
		ArrayList<String> arr=new ArrayList<String>();
		boolean flag = true;		//输入结束标志
		
		while(flag){
			String[] c = scan.nextLine().split(" ");
			if(c[0].equals("I")){
				Input_connection(s, Integer.parseInt(c[1]), Integer.parseInt(c[2]));
			}
			if(c[0].equals("C")){
				boolean connect_flag = Check_connection(s, Integer.parseInt(c[1]), Integer.parseInt(c[2]));
				if(connect_flag){
					arr.add("yes");
				}else{
					arr.add("no");
				}
			}
			if(c[0].equals("S")){
				Check_network(s);
				flag = false;			
			}
		}

		for (int i=0;i<arr.size() ; i++)
        {
            System.out.println(arr.get(i));
        }


		scan.close();
	}

	//1、初始化函数
	public static void gather(int[] s, int n){
		//s = new int[n+1];		//集合使用n+1个数是为了方便操作，角标即为电脑编号
		s[0] = -1;
		//初始化全部为根节点，s值都为-1
		for(int i=1; i<n+1; i++){
			s[i] = -1;
		}
	}

//寻找根节点函数，依据路径压缩方法
	public static int find(int[] s, int a){
		if(s[a]<0){
			return a;
		}else{
			return s[a] = find(s, s[a]);
		}
	}

	//连接函数，输入：两个元素下标
	public static void Input_connection(int[] s, int a, int b){
		//如果两者未连接,则将两者连接
		if(!Check_connection(s,a,b)){
			s[find(s,b)] = a;
		}
	}

	//检查连接函数  判断输入的两个元素的根节点，若相同，则两节点已连接
	public static boolean Check_connection(int[] s, int a, int b){
		int aroot = find(s, a);
		int broot = find(s, b);
		return aroot==broot;
	}

	//输出集合连接函数
	public static void Check_network(int[] s){
		int count = 0;
		for(int i=1; i<s.length; i++){
			if(s[i]==-1){
				count++;
			}
		}
		if(count==1){
			System.out.println("the network is connected.");
		}else{
			 System.out.println("there are "+count+" components.");
		}
	}
}