langmacquoc
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