Untitled

LANG MAC:
Cho bản đồ mạng lưới giao thông giữa các làng mạc. Một vùng được định nghĩa là một tập hợp các làng mà từ bất kỳ một làng nào trong vùng đều có thể đi đến một làng khác trong vùng.

Hãy tính số vùng trong bản đồ, số làng cô lập (làng không có đường đi đến bất kỳ làng khác) và số con đường đóng vai trò là “Cầu” giữa hai vùng (nếu bỏ con đường này đi thì số lượng vùng tăng lên 1).

Input
Dòng đầu có một số T là số lượng test của file input. Mỗi test được bố cục như sau: dòng đầu là một số nguyên dương N (N <= 300) N là số làng, tiếp theo là một ma trân A[i, j] trong đó A[i][j] có giá trị bằng 1 là có đường đi từ làng i tới làng j và 0 nếu không có đường từ làng i tới làng j. Dữ liệu đảm bảo nếu có đường từ làng i tới làng j thì cũng sẽ có đường ngược lại.

Output
Với mỗi test, in ra sốvùng có trên bản đồ, số làng cô lập và số đường đóng vai trò là cầu.

Input:
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

Code: 
#include<iostream>
using namespace std;
int const max_len = 305;
int map[max_len][max_len];              // Map dau vao
int visit[max_len];           // Danh dau dinh
int visitEdge[max_len][max_len];             // Danh dau cac canh
int n;
void Try(int u){
	for( int i= 0; i <n; i++) {
		if (map[u][i] == 1 && !visit[i]) {
			visit[i] = 1;
			Try(i);
		}
	}
}
int getRount(){             // Tra ve so vung trong map
	int ans = 0;
	for ( int i = 0; i<n; i++) {
		if(!visit[i]) {       // dinh i chua duoc xet
			ans++;
			Try(i);
		}
	}
	return ans;
}
void reset() {
	for ( int i = 0; i< n; i++) visit[i] = 0;
}
bool flag2;
void checkBridge(int d1, int d2){
	for( int i = 0; i <n; i++) {
		if (map[d1][i] == 1 && !visit[i]) {
			if ( i == d2) {       // Neu ma tu d1 van di den duoc d2
				flag2 = false;
				return;
			}
			visit[i] = 1;
			checkBridge(i,d2);
			if(!flag2) return;
		}
	}
}
int getBridge(){
	int ans = 0;
	for ( int i = 0; i< n; i++) 
		for ( int j = 0; j< n; j++) 
			visitEdge[i][j] = 0; // reset mang visit canh
	for(int r = 0; r < n; r++) {
		for (int c = 0; c< n; c++) {
			if(map[r][c] == 1 && visitEdge[r][c] == 0) {
				map[r][c]= map[c][r] = 0;         // Thu bo duong di tu r -> c
				visitEdge[r][c] = visitEdge[c][r] = 1;   // Danh dau cap canh da xet
				flag2 = true;
				reset();
				checkBridge(r,c);
				if (flag2) ans++;
				map[r][c]= map[c][r] = 1;
			}
		}
	}
	return ans;
}

int main() {
	//freopen("input.txt","r",stdin);
	int TC;
	cin>>TC;
	int cntAlone;
	int cntEdge;
	for (int t = 1; t <= TC; t++) {
		cntEdge = cntAlone = 0;
		cin>>n;
		for(int i = 0; i <n; i++) {
			bool flag = true;             // Danh dau vung co lap
			for(int j = 0; j< n; j++) {
				cin>> map[i][j];
				if (map[i][j] == 1) {
					cntEdge++;
					flag = false;
				}
			}
			if (flag) cntAlone++;
		}
		cntEdge = cntEdge/2;
		reset();
		int group = getRount();
		int cntBridge = 0;
		if ((n > 2 && cntEdge == (n*(n-1)/2)) || cntEdge == 0) cntBridge = 0;
		else {
			cntBridge = getBridge();
		}
		cout<<group<<" "<<cntAlone<<" "<<cntBridge<<endl;
	}
	return 0;
}