Untitled
unknown
plain_text
a year ago
2.8 kB
2
Indexable
Never
package LangMac; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int N; static int[][] matrix; static int[][] list; static int[] info; static int[][] arr; static int nCanh; static int[] queue; static int head, tail; static int[] visited; static int alone; static int zone; static int bridge; public static void enQueue(int x) { tail++; queue[tail] = x; } public static int deQueue() { head++; return queue[head]; } public static void input(Scanner sc) { N = sc.nextInt(); matrix = new int[N][N]; list = new int[N][N]; info = new int[N]; arr = new int[N * (N - 1) / 2][2]; nCanh = 0; zone = alone = bridge = 0; queue = new int[2 * N * N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { matrix[i][j] = sc.nextInt(); if (matrix[i][j] == 1) { list[i][info[i]] = j; info[i]++; if (matrix[j][i] == 0) { arr[nCanh][0] = i; arr[nCanh][1] = j; nCanh++; } } } } } public static void BFS(int x) { head = tail = -1; enQueue(x); visited[x] = 1; boolean flag = true; while (head != tail) { int temp = deQueue(); for (int i = 0; i < info[temp]; i++) { int a = list[temp][i]; if (visited[a] == 0) { visited[a] = 1; enQueue(a); flag = false; } } } if (flag) { alone++; } } public static boolean BFS_bridge(int x, int y) { head = tail = -1; enQueue(x); visited[x] = 1; while (head != tail) { int temp = deQueue(); for (int i = 0; i < info[temp]; i++) { int a = list[temp][i]; if (visited[a] == 0 && matrix[temp][a] == 1) { visited[a] = 1; if(a == y) { return false; } enQueue(a); } } } return true; } public static void solve() { visited = new int[N]; for (int i = 0; i < N; i++) { if (visited[i] == 0) { BFS(i); zone++; } } for (int i = 0; i < nCanh; i++) { int a = arr[i][0]; int b = arr[i][1]; matrix[a][b] = 0; matrix[b][a] = 0; visited = new int[N]; if (BFS_bridge(a, b)) { bridge++; } matrix[a][b] = 1; matrix[b][a] = 1; } System.out.println(zone + " " + alone + " " + bridge); } public static void main(String[] args) throws FileNotFoundException { // TODO Auto-generated method stub long start = System.currentTimeMillis(); System.setIn(new FileInputStream("input.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int i = 1; i <= T; i++) { input(sc); solve(); } long end = System.currentTimeMillis(); System.out.println((double) (end - start) / 1000); } }