Untitled

mail@pastecode.io avatar
unknown
plain_text
24 days ago
3.5 kB
2
Indexable
Never
import java.util.Scanner;

public class Solution {
	static int N, count1, count2, count3;
	static int[][] map = new int[301][301];
	static Queue queue = new Queue(10000);
	static int[] visit = new int[301];
	static int[] par = new int[301];
	static int[] rank = new int[301];

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int t = 1; t <= T; t++) {
			N = sc.nextInt();

			for (int i = 0; i < N; i++) {
				visit[i] = 0;
				par[i] = i;
				rank[i] = 1;
				for (int j = 0; j < N; j++) {
					map[i][j] = 0;
				}
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
				}
			}

			count1 = count2 = count3 = 0;
			boolean colap = false;
			for (int i = 0; i < N; i++) {
				colap = true;
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 1) {
						colap = false;
						break;
					}
				}

				if (colap) {
					count2++;
				}
			}
			queue.reset();
			for (int i = 0; i < N; i++) {
				visit[i] = 1;
				for (int j = 0; j < N; j++) {
					if (visit[j] == 0 && map[i][j] == 1) {
						queue.push(i, j);
					}
				}
			}

			// find all union
			int x, y, res;
			res = 0;
			int len = queue.length();
			for (int i = 0; i < len; i++) {
				x = queue.valueOf(i)[0];
				y = queue.valueOf(i)[1];
				res += union(x, y);
			}

			count1 = N - res;
			findBridge();
			System.out.println(count1 + " " + count2 + " " + count3);
		}
		sc.close();
	}

	private static void findBridge() {
		// TODO Auto-generated method stub
		int[] temp;

		int e = queue.length();
		int front, u, v, res, x, y, qlen;
		while (e != 0) {
			res = 0;
			temp = queue.pop();
			v = temp[0];
			u = temp[1];
			for (int i = 0; i < N; i++) {
				par[i] = i;
				rank[i] = 1;
			}

			qlen = queue.length();
			front = queue.front();
			for (int i = front; i < qlen + front; i++) {
				x = queue.valueOf(i)[0];
				y = queue.valueOf(i)[1];
				res += union(x, y);
			}

			res = N - res;
			if (res > count1) {
				count3++;
			}
			queue.push(v, u);
			e--;
		}
	}

	private static int union(int v, int u) {
		// TODO Auto-generated method stub
		int p1 = find(v);
		int p2 = find(u);

		if (p1 == p2)
			return 0;

		if (rank[p1] >= rank[p2]) {
			par[p2] = p1;
			rank[p1] += rank[p2];
		} else {
			par[p1] = p2;
			rank[p2] += rank[p1];
		}

		return 1;
	}

	private static int find(int x) {
		// TODO Auto-generated method stub
		// find root
		int p = par[x];

		while (p != par[p]) {
			p = par[par[p]];

		}

		return p;
	}

}

class Queue {
	private int front, rear, capacity;
	private int queue[][];
	private int[] res;

	Queue(int c) {
		front = rear = 0;
		capacity = c;
		queue = new int[capacity][2];
		res = new int[2];
	};

	void push(int x, int y) {
		queue[rear][0] = x;
		queue[rear][1] = y;
		if (rear == capacity - 1)
			rear = 0;
		rear++;
	};

	int[] pop() {
		res[0] = queue[front][0];
		res[1] = queue[front][1];

		if (front == capacity - 1)
			front = 0;
		front++;
		return res;
	};

	void reset() {
		front = rear = 0;
	};

	boolean empty() {
		return front == rear;
	};

	int[] valueOf(int index) {
		return queue[index];
	};

	int length() {
		return rear - front;
	};

	int front() {
		return front;
	};

	int rear() {
		return rear;
	};
}