Untitled
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