Untitled

 avatar
unknown
plain_text
2 years ago
6.5 kB
3
Indexable
Làng mạc
Cho bản đồ mạng lưới giao thông giữa các làng mạc. Một vùng được định nghĩa là một tập hợp các làng mà từ bất kỳ một làng nào trong vùng đều có thể đi đến một làng khác trong vùng.

Hãy tính số vùng trong bản đồ, số làng cô lập (làng không có đường đi đến bất kỳ làng khác) và số con đường đóng vai trò là “Cầu” giữa hai vùng (nếu bỏ con đường này đi thì số lượng vùng tăng lên 1).

Input

Dòng đầu có một số T là số lượng test của file input. Mỗi test được bố cục như sau: dòng đầu là một số nguyên dương N (N <= 300) N là số làng, tiếp theo là một ma trân A[i, j] trong đó A[i][j] có giá trị bằng 1 là có đường đi từ làng i tới làng j và 0 nếu không có đường từ làng i tới làng j. Dữ liệu đảm bảo nếu có đường từ làng i tới làng j thì cũng sẽ có đường ngược lại.

Output

Với mỗi test, in ra sốvùng có trên bản đồ, số làng cô lập và số đường đóng vai trò là cầu.

/** Solution 1 **/ Chua ra

package Lesson_10;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Lang_mac {
	static int T, N, v, l, c, nodeV, nodeC;
	static int map[][], index[];
	static boolean visited[], visitedC[];
	static int count_v, count_c;
	
	public static class Queue{
		static int front, rear, Data[];
		
		public Queue() {
			this.front = this.rear = -1;
			Data = new int[1000];
		}
		
		public static void reset(){
			front = rear = -1;
		}
		
		public static void enQueue(int value){
			Data[++rear] = value;
		}
		
		public static int deQueue(){
			return Data[++front];
		}
		
		public static boolean is_Empty(){
			if(front == rear) return true;
			return false;
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException{
		System.setIn(new FileInputStream("Lang_mac"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++){
			N = scanner.nextInt();
			map = new int[N][N];
			index = new int[N];
			visited = new boolean[N];
			visitedC = new boolean[N];
			int value;
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					value = scanner.nextInt();
					if(value == 1){
						map[i][index[i]++] = j;
					}
				}
			}
			
			Queue vQueue = new Queue();
			Queue cQueue = new Queue();
			v = l = c = 0;
			// Duyet tung node
			for(int k = 0; k < N; k++){
				count_v = count_c = 0;
				// Kiem tra lang co lap
				if(index[k] == 0){
					v++;
					l++; 
					continue;
				}
				
				// Dem so cau
				cQueue.enQueue(k);
				visitedC[k] = true;
				while(!cQueue.is_Empty()){
					nodeC = cQueue.deQueue();
					for(int j = 0; j < index[nodeC]; j++){
						map[nodeC][j] = 0;
						
					}
				}
			
				vQueue.enQueue(k);
				visited[k] = true;
				while(!vQueue.is_Empty()){
					nodeV = vQueue.deQueue();
					
					// Duyet cac canh lien ke co value = 1
					for(int j = 0; j < index[nodeV]; j++){
						if(!visited[ map[nodeV][j] ]){
							count_v++;
							vQueue.enQueue(map[nodeV][j]);
							visited[map[nodeV][j]] = true;
						}
						
					}
				}
				if(count_v >= 1) v++;
				
			}
			
			
		
			System.out.println("So vung = " + v);
			System.out.println("So lang co lap = " + l);
			System.out.println("So cau = " + c);
			System.out.println();
		}
	}

}

// Solution 2

package Lesson_10;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Lang_mac_2 {
	static int T, N, v, l, c, nodeC, nodeV;
	static int map[][];
	static boolean visited[], visitedC[];
	static int count_v, count_c;
	
	public static class Queue{
		static int front, rear, Data[];
		
		public Queue() {
			this.front = this.rear = -1;
			Data = new int[1000];
		}
		
		public static void reset(){
			front = rear = -1;
		}
		
		public static void enQueue(int value){
			Data[++rear] = value;
		}
		
		public static int deQueue(){
			return Data[++front];
		}
		
		public static boolean is_Empty(){
			if(front == rear) return true;
			return false;
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException{
		System.setIn(new FileInputStream("Lang_mac"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++){
			N = scanner.nextInt();
			map = new int[N][N];
			visited = new boolean[N];
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					map[i][j] = scanner.nextInt();
				}
			}
			Queue cQueue = new Queue();
			Queue vQueue = new Queue();
			v = l = c = 0;
			int check, count;
			// Tinh so vung, lang co lap
			for(int i = 0; i < N; i++){
				count = 0;
				for(int k = 0; k < N; k++){
					if(map[i][k] == 0){
						count++;
					}
				}
				if(count == N){
					v++;
					l++;
				}
				vQueue.enQueue(i);
				visited[i]= true;
				check = 0;
				while(!vQueue.is_Empty()){
					nodeV = vQueue.deQueue();
					for(int j = 0; j < N; j++){
						if(map[nodeV][j] == 1 && visited[j] == false){
							visited[j] = true;
							vQueue.enQueue(j);
							check++;
						}
					}
				}
				if(check != 0) v++;
			}
			// Tinh cau
			boolean flat = true;
			
			for(int i = 0; i < N; i++){
				for(int j = i; j < N; j++){
					if(map[i][j] == 1){
						flat = true;
						map[i][j] = 0;
						map[j][i] = 0;
						visitedC = new boolean[N];
					cQueue.reset();
					cQueue.enQueue(i);
					visitedC[i] = true;
					while(!cQueue.is_Empty() && flat){
						int cV = cQueue.deQueue();
						
						for(int k = 0; k < N; k++){
							if(map[cV][k] == 1 && !visitedC[k]){
								cQueue.enQueue(k);
								visitedC[k] = true;
							}
							if(map[cV][j] == 1){
								flat = false;
							}
						}
					}
					if(flat) c++;
					map[i][j] = 1;
					map[j][i] = 1;
					}
				}
			}
			
			
			// Tinh so cau
			System.out.println(v + " " + l + " " + c);
		}
	}

}

2
5
0 1 0 1 0
1 0 0 1 0
0 0 0 0 1
1 1 0 0 0
0 0 1 0 0
7
0 0 0 1 0 0 1
0 0 0 1 0 0 0
0 0 0 0 1 0 0
1 1 0 0 0 0 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0
1 0 0 1 0 0 0
Editor is loading...