Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
3.4 kB
1
Indexable
Never
package buoi_10;

import java.util.Scanner;
import java.io.FileInputStream;


import advanced_training.FixedSizeArrayQueue;

/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class LangMac
{
	static FixedSizeArrayQueue<Integer> queue = new FixedSizeArrayQueue<Integer>(301);
	static int timeDfs;
	static int cau;
	static int[] low;
	static int[] num;
	
	static void dfs (int u, int pre) {
		num[u] = low[u] = ++timeDfs;
		for (int i = 0; i < low.length; ++i) {
			if (i == pre) continue;
			if (num[i] == 0) {
				dfs(i, u);
				low[u] = Math.min(low[u], low[i]);
				if (low[u] == low[i]) cau++;
			} else {
				low[u] = Math.min(low[u], num[i]); 
			}
		}
	}
	
	
	public static void main(String args[]) throws Exception
	{
		/*
		   The method below means that the program will read from input.txt, instead of standard(keyboard) input.
		   To test your program, you may save input data in input.txt file,
		   and call below method to read from the file when using nextInt() method.
		   You may remove the comment symbols(//) in the below statement and use it.
		   But before submission, you must remove the freopen function or rewrite comment symbols(//).
		 */
		System.setIn(new FileInputStream("input.txt"));

		/*
		   Make new scanner from standard input System.in, and read data.
		 */
		Scanner sc = new Scanner(System.in);
		int T;
		int co_lap,vung;
		int[] visited;
		boolean[] isCau;
		T=sc.nextInt();
		/*
   			Read each test case from standard input.
   		*/
		
//		long begin = System.currentTimeMillis();
		for(int test_case = 1; test_case <= T; test_case++)
		{

			/////////////////////////////////////////////////////////////////////////////////////////////
			/*
				Please, implement your algorithm from this section.
			*/
			/////////////////////////////////////////////////////////////////////////////////////////////
			int n = sc.nextInt();
			int[][] mat = new int[n][n];
			
			for (int  i = 0; i < n; ++i) {
				for (int  j = 0; j < n; ++j) {
					mat[i][j] = sc.nextInt(); 
				}
			}
			
			vung = 0;
			co_lap = 0;
			visited = new int[n];
			for (int i = 0; i < n; ++i) {
				boolean flag_co_lap = true;
				boolean flag_vung = false;
				for (int j = 0; j < n; ++j){
					if (mat[i][j] != 0) flag_co_lap = false;
					if (mat[i][j] != 0 && visited[i] != 0) flag_vung = true;
				}
				if (flag_co_lap) {
					co_lap++;
					vung++;
					visited[i] = vung;
				} else {
					if (!flag_vung) {
						vung++;
						queue.reset();
						queue.enqueue(i);
						visited[i] = vung; 
						while (!queue.isEmpty()) {
							int temp = queue.dequeue();
							for (int j = 0; j < n; ++j) {
								if (j != temp && visited[j] == 0 && mat[temp][j] != 0) {
									visited[j] = vung;
									queue.enqueue(j);
								}
							}
						}
					}
					// cau ?
				}
			}
			
			timeDfs = 0;
			cau = 0;
			low = new int[n];
			num = new int[n];
			for (int j = 0; j < n; ++j) {
				if(num[j] == 0) dfs(j, j);
			}
			
			
			// Print the answer to standard output(screen).
			System.out.println(vung + " " + co_lap + " " + cau);
		}
//		System.out.println(System.currentTimeMillis()-begin);
	}
	
}

Leave a Comment