Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.6 kB
1
Indexable
Never
#include<iostream>
using namespace std;

int N;
int map[105][105]; // map

int queue[1000000];
int r = -1, f = -1;
bool visited[105]; // mang visited cac dinh da di qua

int mapAns[105]; // mang luu listAdjt qua theo couting sort

void push(int x)
{
	r++;
	queue[r] = x;
}

void pop(int &x)
{
	f++;
	x = queue[f];
}

void BFS(int node)
{
	// must reset queue
	push(node);
	visited[node] = true;
	int pre;
	while(r != f)
	{
		pop(pre);
		for(int i = 1; i <= N; i++)
		{
			if(map[pre][i] == 1 && visited[i] == false)
			{
				visited[i] = true;
				push(i);
			}
		}
	}
}

void resetQueue()
{
	r = f = -1;
	for(int i = 0; i < 105; i++)
	{
		visited[i] = false;
	}
}

void resetAns()
{
	for(int i = 0; i< 105; i++)
	{
		mapAns[i] = 0;
	}
}

int main()
{
	//freopen("Text.txt","r",stdin);
	int T;
	cin>>T;

	for(int tc =1; tc <= T; tc++)
	{
	// input
		cin>>N;
		for(int i = 1; i <= N; i++)
			for(int j = 1; j<= N; j++)
			cin>>map[i][j];
		
		// reset
		resetAns();
		// process
		for(int i = 1; i <= N; i++)
		{
			int countArea = 0;
			visited[i] = true;
			for(int j = 1; j<= N; j++)
			{
				if(visited[j] == false)
				{
					BFS(j);
					countArea++;
				}
			}
			resetQueue();
			mapAns[i] = countArea;
		}
		// tim max ans trong map ans
		int maxAns = 0;
		int ans = 0;
		for(int i = 1; i<= N; i++)
		{
			if(mapAns[i] > maxAns)
			{
				maxAns = mapAns[i];
				ans = i;
			}
		}
		if(maxAns == 1)
			ans = 0;
		cout << ans<<endl;
	}
	return 0;
}