Untitled
unknown
plain_text
6 months ago
2.5 kB
7
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; } }