# 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;
};
}
```