Untitled

mail@pastecode.io avatar
unknown
plain_text
13 days ago
2.4 kB
0
Indexable
Never
package Queue;

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

public class Moi_Dam_Cuoi {
	static int T, nodes, edges;
	static int nodeStart, nodeEnd;
	static int map[][], temp[][];
	static int count, cNode, nNode;
	static boolean visited[];
	
	public static class Queue{
		static int front, rear, Data[];
		
		public Queue() {
			this.front = this.rear = -1;
			Data = new int[1000000];
		}
		
		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() {
			return front == rear;
		}
	}
	
	public static void countNode() {
		Queue queue = new Queue();
		
		for(int i = 1; i <= nodes; i++) {
			if(i == nodeStart || i == nodeEnd) continue;
			else {
				for(int j = 1; j <= nodes; j++) {
					temp[i][j] = 0;
					temp[j][i] = 0;
				}
				queue.reset();
				visited = new boolean[nodes+1];
				queue.enQueue(nodeStart);
				visited[nodeStart] = true;
				boolean check = false;
				while(!queue.is_Empty()) {
					cNode = queue.deQueue();
					for(int t = 1; t <= nodes; t++) {
						if(temp[cNode][t] == 1 && !visited[t]) {
							visited[t] = true;
							queue.enQueue(t);
							}
							
						if(temp[cNode][nodeEnd] == 1) {
							check = true;
							break;
						}
					}
					if(check) break;
				}
				if(!check) count++;
				for(int j = 1; j <= nodes; j++) {
					temp[i][j] = map[i][j];
					temp[j][i] = map[j][i];
				}
				
			}
		}
		
		
	}
	
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src/Queue/Moi_Dam_Cuoi"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc ++) {
			nodes = scanner.nextInt();
			edges = scanner.nextInt();
			nodeStart = scanner.nextInt();
			nodeEnd = scanner.nextInt();
			map = new int[nodes+1][nodes+1];
			temp = new int[nodes+1][nodes+1];
			int	x, y ;
			for(int i = 1; i <= edges; i++) {
				x = scanner.nextInt();
				y = scanner.nextInt();
				map[x][y] = 1;
				temp[x][y] = 1;
			}
			
			count = 0;
			countNode();
			System.out.println(count);
			
		}
	}

}
Leave a Comment