langmacquoc

 avatar
quoc14
c_cpp
a month ago
1.9 kB
0
Indexable
Never
caidat
#include <iostream>
using namespace std;
int n;
int a[1000][1000];
int ans_vung = 0;
		
int ans_cau = 0;
int ans_lang = 0;

int check[305];

int visited[305];



void dfs(int i) {
	visited[i] = 1;
	for (int k = 1; k <= n; k++) {
		if (a[i][k] == 1 && visited[k] == 0) {
			dfs(k);
		}
	}	
}

void solve(){
	// Lang
	for (int i = 1; i <= n; i++) {
		int check = 0;
		for (int j = 1; j <= n; j++) {
			if (a[i][j] == 1) {
				check = 1;
					
			}
		}
		if (check == 0) {
			ans_lang++;
		}
	}
		
	// reset vs
	for (int i = 0; i< 305; i++) {
		visited[i] = 0;
	}
		
		
		
	// Area
	for (int i = 1; i <= n; i++) {
		if (visited[i] == 0) {
			ans_vung++;
			dfs(i);
		}
	}
		
	// bridge
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (a[i][j] == 1) {
				for (int k = 1; k <= n; k++) {
					visited[k] = 0;
				}
				a[i][j] = 0;
				a[j][i] = 0;
				dfs(i);
				if (visited[j] == 0) {
					ans_cau++;
				}
				a[i][j] = 1;
				a[j][i] = 1;
				
			}
		}
	}
	cout << ans_vung << " " << ans_lang << " " << ans_cau << endl;
}

int main() {
	//freopen("input.txt", "r", stdin);
	int t; cin >> t;

	for (int test = 1; test <= t; test++) {
		int c0 = 0, c1 = 0;
		cin >> n;
		
		for (int i = 1; i <= n; i++) {

			for (int j = 1; j <= n; j++) {
				cin >> a[i][j];

				if(i == j) a[i][j] = 0;
				if(a[i][j]) c1++;
				else c0++;
			}
			
		}

		// initial
		ans_vung = 0;
		ans_cau = 0;
		ans_lang = 0;
		
		if(c1 == n*n - n){
			cout << 1 << " " << 0 << " " << 0 << endl;
		} else if(c0 == n*n){
			cout << n << " " << n << " " << 0 << endl;
		} else{
			solve();
		}
	}
	return 0;
}

2

5

0 1 0 1 0

1 0 0 1 0

0 0 0 0 1

1 1 0 0 0

0 0 1 0 0

7

0 0 0 1 0 0 1

0 0 0 1 0 0 0

0 0 0 0 1 0 0

1 1 0 0 0 0 1

0 0 1 0 0 0 0

0 0 0 0 0 0 0

1 0 0 1 0 0 0

 

Output

2 0 1

3 1 2
Leave a Comment