Untitled
plain_text
17 days ago
2.6 kB
1
Indexable
Never
package di_an_cuoi; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, m, check, count, res; static int[][] a; static int[] parent, visit1, visit2; static void BFS1(int start, int end) { int[] q = new int[1000]; int front = 0, rear = 1; q[front] = start; visit1[start] = 1; while (front < rear) { int x = q[front]; for (int i = 1; i <= n; i++) { if (a[x][i] == 1 && visit1[i] == 0) { q[rear] = i; rear++; visit1[i] = 1; parent[i] = x; if (visit1[end] == 1) { return; } } } front++; } } static void BFS2(int start, int end) { int[] q = new int[1000]; int front = 0, rear = 1; q[front] = start; visit2[start] = 1; while (front < rear) { if(visit1[q[front]] == 0){ for (int i = front; i < rear; i++) { if (visit1[q[i]] == 1) { int x = q[front]; q[front] = q[i]; q[i] = x; break; } } } int top = q[front]; for (int i = 1; i <= n; i++) { if (a[top][i] == 1 && visit2[i] == 0) { q[rear] = i; rear++; visit2[i] = 1; parent[i] = top; if(visit2[end] == 1){ return; } } } front++; } } public static void main(String[] args) { try { System.setIn(new FileInputStream("input.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner scanner = new Scanner(System.in); int test = scanner.nextInt(); for (int t = 1; t <= test; t++) { n = scanner.nextInt(); m = scanner.nextInt(); a = new int[n + 1][n + 1]; for (int i = 0; i < m; i++) { a[scanner.nextInt()][scanner.nextInt()] = 1; } count = 0; parent = new int[n+1]; visit1 = new int[n + 1]; visit2 = new int[n + 1]; BFS1(1, 2); visit1 = new int[n+1]; int x = 2; while(x != 1){ visit1[parent[x]] = 1; x = parent[x]; } // for (int i = 1;i<=n; i++) { // System.out.print(visit1[i] + " "); // } // System.out.println(); BFS2(2, 1); visit2 = new int[n+1]; x = 1; while(x != 2){ visit2[parent[x]] = 1; x = parent[x]; } visit1[1] = 1; visit1[2] = 1; for (int i = 1; i <= n; i++) { if (visit1[i] == 1 || visit2[i] == 1) { count++; } } System.out.println(count); } scanner.close(); } }