Untitled

mail@pastecode.io avatar
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);
	}

}