Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.1 kB
3
Indexable
Never
#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 dc xet
			ans++;
			Try(i);
		}

	}
	return ans;
}
void reset(){
	for(int i=0; i<n;i++){
		visit[i]=0;           // reset mangvisit
	}

}
bool flag2;
void checkBrigde(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 dc den d2
				flag2=false;
				return;
			}

			visit[i]=1;
			checkBrigde(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 mangvisit
		}
	}
	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 den c
				visitEdge[r][c]=visitEdge[c][r]=1;
				flag2=true;
				reset();
				checkBrigde(r,c);
				if(flag2) ans++;
				map[r][c]=map[c][r]=1;
			}

		}

	}
	return ans;

}



int main()
{
	int test_case;
	int T;
	int Answer;
	int cntAlone;
	int cntEdge;
	//freopen("text.txt", "r", stdin);
	cin >> T;

	for(test_case = 1; test_case <= T; ++test_case)
	{


		cin>>n;
		cntAlone=0;
		cntEdge=0;
		for(int i=0; i<n;i++){
			bool flag=true; // danh dau vung cco 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;
}