Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.5 kB
8
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class LangMac {
	static int n;
	static int a[][];
	static int visit[];
	static int vung, colap, cau;
	static boolean isCau;

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("LangMac"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		Scanner sc = new Scanner(System.in);
		int numTest = sc.nextInt();
		for (int tc = 1; tc <= numTest; tc++) {
			n = sc.nextInt();
			a = new int[n + 2][n + 2];

			boolean isMang0 = true;
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					a[i][j] = sc.nextInt();
					if (a[i][j] != 0)
						isMang0 = false;
				}

			}

			visit = new int[n + 1];
			vung = 0;
			boolean isMang1 = true;
			if (isMang0) {
				System.out.println(n + " " + n + " " + 0);
			} else {
				for (int i = 1; i <= n; i++) {
					for (int j = 1; j <= n; j++) {
						if (a[i][j] == 0 && i != j)// check duong cheo chinh
							isMang1 = false;
					}
				}
				if (isMang1)
					System.out.println(1 + " " + 0 + " " + 0);
			}
			if (!isMang0 && !isMang1) {
				for (int i = 1; i <= n; i++) { // theo cot
					if (visit[i] == 0) {
						DFS(i);
						++vung;
					}
				}

				// System.out.println("Vung = " + vung);
				colap = n;

				for (int i = 1; i <= n; i++) {
					for (int j = 1; j <= n; j++)
						if (a[i][j] == 1) {
							colap--;
							break;
						}
				}
				cau = 0;
				for (int i = 1; i <= n; i++) {
					for (int j = i + 1; j <= n; j++)
						if (a[i][j] == 1) {
							isCau = true;
							visit = new int[n + 1];
							a[i][j] = 0;// cat cau
							DFS(i, j);
							if (isCau) {
								// System.out.println("i = "+i +"; j = "+j);
								++cau;
							}

							a[i][j] = 1;// tra lai cau
						}
					//
				}
				System.out.println(vung + " " + colap + " " + cau);
			}
		}
	}

	public static void DFS(int dinhNguon) {
		visit[dinhNguon] = 1;

		for (int i = 1; i <= n; i++) {
			if (a[dinhNguon][i] == 1 && visit[i] == 0) {
				DFS(i);
			}
		}
	}

	public static boolean DFS(int dinhNguon, int dinhDich) {
		if (dinhNguon == dinhDich) {
			isCau = false;
			return false;
		}
		visit[dinhNguon] = 1;
		for (int i = 1; i <= n; i++) {
			if (!isCau) {
				return false; //
			}
			if (a[dinhNguon][i] == 1 && visit[i] == 0) {
				DFS(i, dinhDich);

			}

		}
		return true;
	}
}