Untitled
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; }; }