Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.7 kB
1
Indexable
Never
#include<iostream>
using namespace std;
int start, rear;
int ke[305][305];
int countt[305];
int queue[90005];
int visited[305];
int n;
int vung, colap, cau;
void timvung(int u){
	while(start!=rear){
		int x = queue[start];
		start++;
		for(int i=0; i<countt[x]; i++){
			if(visited[ke[x][i]]==0){
				queue[rear]=ke[x][i];
				rear++;
				visited[ke[x][i]]=1;
			}
		}
	}
}
int timcau(int dau, int cuoi){
	while(start!=rear){
		int x = queue[start];
		start++;
		for(int i=0; i<countt[x]; i++){
			if(ke[x][i]!=-1){
				if(ke[x][i]==cuoi) return 0;
				if(visited[ke[x][i]]==0){
					queue[rear]=ke[x][i];
					rear++;
					visited[ke[x][i]]=1;
				}
			}
		}
	}
	return 1;
}
int main(){
//	freopen("in.txt", "r", stdin);
	int t;
	cin>>t;
	for(int tc=1; tc<=t; tc++){
		cin>>n;
		vung=0;
		colap=0;
		cau=0;
		for(int i=0; i<n; i++){
			countt[i]=0;
			visited[i]=0;
		}
		int x;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				cin>>x;
				if(x==1) {
					ke[i][countt[i]++] = j;
				}
			}
		}
		for(int i=0; i<n; i++){
			if(countt[i]==0) colap++;
		}
		for(int i=0; i<n; i++){
			start=0; rear=1;
			queue[0] = i;
			if(visited[i]==0){
				timvung(i);
				vung++;
			}
		}
		for(int i=0; i<n; i++) visited[i]=0;
		for(int i=0; i<n; i++){
			for(int j = 0; j<countt[i]; j++){
				start=0; rear=1;
				queue[0] = i;
				int h = ke[i][j];
				int q;
				
				for(int z=0; z<countt[h]; z++){
					if(ke[h][z]==i){
						q = z;
					}
				}
				ke[i][j] = -1;
				ke[h][q]=-1;
				cau+= timcau(i, h);
				ke[i][j]=h;
				ke[h][q]=i;
				for(int z=0; z<n; z++) visited[z]=0;
			}
		}
		cout<<vung<<" "<<colap<<" "<<cau/2<<endl;
	}
	return 0;
}