Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.4 kB
3
Indexable
Never
//Pha huy he thong dien
#include <iostream>
using namespace std;
#define SIZE 105

int N, res;
int maTranKe[SIZE][SIZE], visited[SIZE];


void markLienThong(int x) {
	visited[x] = 1;
	for (int i = 1; i <= N; i++) {
		if (visited[i] == 0 && maTranKe[x][i] == 1) {
			markLienThong(i);
		}
	}
}

void destroy() {
	int originalIslandGroup = 0;
	for (int i = 1; i <= N; i++) {
		if (visited[i] == 0) {
			markLienThong(i);
			originalIslandGroup++;
		}
	}
	
	int tmp[SIZE][SIZE] = {0};
	int groupMax = 0;

	for (int i = 1; i <= N; i++) {
		
		for (int i = 1; i <= N; i++) {
			visited[i] = 0;
		}

		visited[i] = 1;

		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				tmp[j][k] = maTranKe[j][k];
			}
		}

		for (int j = 1; j <= N; j++) {
			tmp[i][j] = tmp[j][i] = 0;
		}

		int newGroup = 0;
		for (int j = 1; j <= N; j++) {
			if (visited[j] == 0) {
				markLienThong(j);
				newGroup++;
			}
		}

		if (newGroup != originalIslandGroup && newGroup > groupMax) {
			groupMax = newGroup;
			res = i;
		}
	}
		

}


int main() {
	//freopen("in.txt", "r", stdin);
	int T;
	cin >> T;
	int tc = 1;
	while(T--) {
		res = 0;
		cin >> N;
		for (int i = 1; i <= N; i++) {
			visited[i] = 0;
			for (int j = 1; j <= N; j++) {
				cin >> maTranKe[i][j];
			}
		}

		destroy();

		cout << res << endl;
	}
	return 0;
}

Leave a Comment