Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
3.0 kB
1
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class bai2 {
    static int n;

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("Text"));
        Scanner scanner = new Scanner(System.in);
        int tc = scanner.nextInt();

        for (int Case = 1; Case <= tc; Case++) {
            n = scanner.nextInt();
            int[][] arr = new int[n][n];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    arr[i][j] = scanner.nextInt();
                }
            }

            int[] result = find(arr);
            System.out.println(result[0] + " " + result[1] + " " + result[2]);
        }
    }

    public static int[] find(int[][] arr) {
        int vung = 0;
        int soluong = 0;
        int cau = 0;
        int[] visited = new int[n];
        boolean[][] check = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            if (visited[i] == 0) {
                vung++;
                BFS(arr, i, visited);
            }
        }

        for (int i = 0; i < n; i++) {
            if (visited[i] == 0) {
                soluong++;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i][j] == 1 && !check[i][j]) {
                    arr[i][j] = arr[j][i] = 0;
                    check[i][j] = check[j][i] = true;
                    boolean[] tempVisited = new boolean[n];
                    if (BFS_cau(arr, i, j, tempVisited)) {
                        cau++;
                    }
                    arr[i][j] = arr[j][i] = 1;
                }
            }
        }

        int[] result = {vung, soluong, cau};
        return result;
    }

    public static void BFS(int[][] arr, int start, int[] visited) {
        int[] queue = new int[n];
        int front = 0, rear = -1;
        queue[++rear] = start;
        visited[start] = 0;

        while (front <= rear) {
            int node = queue[front++];
            for (int i = 0; i < n; i++) {
                if (arr[node][i] == 1 && visited[i] == 0) {
                    visited[i] = visited[node] + 1;
                    queue[++rear] = i;
                }
            }
        }
    }

    public static boolean BFS_cau(int[][] arr, int start, int end, boolean[] visited) {
        int[] queue = new int[n];
        int front = 0, rear = -1;
        queue[++rear] = start;
        visited[start] = true;

        while (front <= rear) {
            int node = queue[front++];
            if (node == end) {
                return false;
            }
            for (int i = 0; i < n; i++) {
                if (arr[node][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue[++rear] = i;
                }
            }
        }
        return true;
    }
}