Untitled

#include <iostream>

using namespace std;
//Implement Queue------------------------------------------------------------------------------------------------------------------------
struct Node {
	int data;
	Node* next;
	Node* prev;

	Node (int _data = NULL, Node* _next = NULL, Node* _prev = NULL) {
		data = _data;
		next = _next;
		prev = _prev;
	}
};

struct Queue {
	Node* head;
	Node* tail;
	int size;

	Queue() {
		head = NULL;
		tail = NULL;
		size = 0;
	}

	void enq(int newData) {
		if (size == 0) {
			head = new Node(newData, NULL, NULL);
			tail = head;
			size++;
			return;
		}

		Node* newNode = new Node(newData);
		head->prev = newNode;
		newNode->next = head;
		head = newNode;

		size++;
	}

	int deq() {
		if (size == 0) {
			cout << endl << "Queue is empty you cannot dequeue.";
			return 0;
		}

		if (size == 1) {
			Node* oldTail = tail;
			int oldData = tail->data;
			head = NULL;
			tail = NULL;
			delete oldTail;

			size--;
			return oldData;
		}

		Node* oldTail = tail;
		int oldData = tail->data;

		oldTail->prev->next = NULL;
		tail = oldTail->prev;
		delete oldTail;

		size--;
		return oldData;
	}

	void printQueue() {
		if (size == 0) {
			cout << endl << "Queue have 0 node, nothing to print." << endl;
			return;
		}

		Node* thisNode = head;
		while (thisNode != NULL)
		{
			cout << thisNode->data << "->";
			thisNode = thisNode->next;
		}
	}
};

//Implement Stack------------------------------------------------------------------------------------------------------------------------
const int TACKSIZE = 100000;

struct Stack {
	int top;
	int stack[TACKSIZE];

	Stack() {
		top = -1;
	}

	bool isEmpty() {
		return top == -1;
	}

	bool isFull() {
		return top == TACKSIZE - 1;
	}

	void push(int x) {
		if (this->isFull()) {
			cout << "Stack is filled, cannot push any more" << endl;
			return;
		}

		top++;
		stack[top] = x;
	}

	int pop() {
		if (this->isEmpty()) {
			cout << "Already empty, nothing to pop" << endl;
			return NULL;
		}

		top--;
		return stack[top + 1];
	}

	int peek() {
		if (this->isEmpty()) return NULL;
		return stack[top];
	}

	void printStack() {
		cout << "Tail to head: ";
		for (int i = 0; i <= top; i++)
		{
			cout << stack[i] << " ";
		}
		cout << endl;
	}
};

//Main code below---------------------------------------------------------------------------------------------------------------------

void reset();

const int SIZE = 300;
int n;
bool villageMap[SIZE][SIZE];
bool visited[SIZE];
int save, vlgID;
bool bridge[SIZE][SIZE];

int countIsolateVillage() {
	int count = 0;
	int total;
	for (int i = 0; i < n; i++)
	{
		total = 0;
		for (int e = 0; e < n; e++)
		{
			total += villageMap[i][e];
		}
		if (total == 0) count++;
	}

	return count;
}

void checkVillageArea(int villageID) {          //đánh dấu hết các làng có đường đi đến làng này
	Queue queue;
	queue.enq(villageID);

	while (queue.size != 0)
	{
		int thisVillage = queue.deq();

		for (int i = 0; i < n; i++)
		{
			if (visited[i] == true) continue;
			if (villageMap[i][thisVillage] == 1) {
				visited[i] = true;
				queue.enq(i);
			}
		}
	}

}

int numberOfArea() {   //xet từng chưa đánh dấu -> đánh dấu hết các làng thuộc cùng vùng làng đó -> xét làng tiếp theo chưa đánh dấu
	reset();
	int areaCount = 0;

	for (int i = 0; i < n; i++) //xét từng làng
	{
		if (visited[i] == true) continue; //nếu đã đánh dấu thì bỏ qua
		visited[i] = true;
		checkVillageArea(i);
		areaCount++;
	}
	return areaCount;
}

int countBridge();

bool isBridge(int vlg1, int vlg2);

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t, rawt;
	cin >> t;
	rawt = t;
	while (t--)
	{
		cin >> n;

		for (int i = 0; i < n; i++)
		{
			for (int e = 0; e < n; e++)
			{
				cin >> villageMap[i][e];
			}
		}
		//input done
        
		int areaCount = numberOfArea();
		int bridgeCount = countBridge();

		
		cout << areaCount << " " << countIsolateVillage() << " " << bridgeCount << endl;
	}
}

void reset() {
	for (int i = 0; i < n; i++)
	{
		visited[i] = false;
	}
}

int countBridge() {
	int count = 0;
	for (int i = 0; i < n; i++)                       //xét từng cầu
	{
		for (int e = i + 1; e < n; e++)
		{
			if (villageMap[i][e] == 1) {
				if (isBridge(i,e)) count++;
			}
		}
	}
	return count;
}

bool isBridge(int vlg1, int vlg2) {      
	reset();
	villageMap[vlg1][vlg2] = 0;                //Tạm thời bỏ đường này đi
	villageMap[vlg2][vlg1] = 0;

	Stack stack;
	stack.push(vlg1);
	
	while (!stack.isEmpty()) 
	{
		vlgID = stack.pop();
		if (visited[vlgID] == true) continue;
		visited[vlgID] = true;
		
		for (int i = 0; i < n; i++)
		{
			if (villageMap[vlgID][i] == 1) {  
				if (i == vlg2) {
					villageMap[vlg1][vlg2] = 1;					
					villageMap[vlg2][vlg1] = 1;         
					return false;
				} 

				stack.push(i);
			}
		}
	}

	villageMap[vlg1][vlg2] = 1;              
	villageMap[vlg2][vlg1] = 1;

	return true;
}