Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
2.2 kB
2
Indexable
Never
#include <iostream>
using namespace std;

int n;
int arr[301][301];
bool visited[301][301];
int len[301];
int dd[301];
bool flag;

typedef struct Queue
{
	int front, rear;
	int data[90001];
};

void init(Queue& Q) {
	Q.front = Q.rear = -1;
}

void push(Queue& Q, int value) {
	Q.rear++;
	Q.data[Q.rear] = value;
}

int top(Queue& Q) {
	int temp;
	Q.front++;
	temp = Q.data[Q.front];
	Q.front--;
	return temp;
}

void pop(Queue& Q) {
	Q.front++;
}

bool empty(Queue& Q) {
	if (Q.front == Q.rear)
		return true;
	return false;
}

Queue Q;

void BFS(int u, int v) {

	init(Q);

	push(Q, u);

	dd[u] = 1;

	while (!empty(Q)) {
		int x = top(Q);
		pop(Q);

		if (x == v) {
			flag = false;
			return;
		}

		for (int i = 0; i < len[x]; i++) {
			int y = arr[x][i];
			if (dd[y] == 0 && visited[x][y] == true) {
				dd[y] = 1;
				push(Q, y);
			}
		}
	}
}

void DFS(int u) {
	for (int i = 0; i < len[u]; i++) {
		int x = u;
		int y = arr[u][i];
		if (visited[x][y] == true && dd[y] == 0) {
			dd[y] = 1;
			DFS(y);
		}
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {

		cin >> n;
		int m;
		for (int i = 0; i < n; i++) {
			int c = 0;
			for (int j = 0; j < n; j++) {
				cin >> m;
				if (m == 1) {
					arr[i][c++] = j;
					visited[i][j] = true;
					visited[j][i] = true;
				}
			}
			len[i] = c;
		}

		int demLT = 0;

		for (int k = 0; k < n; k++) {
			dd[k] = 0;
		}
		for (int i = 0; i < n; i++) {
			if (dd[i] == 0) {
				demLT++;
				dd[i] = 1;
				DFS(i);
			}
		}

		int demCL = 0;
		for (int i = 0; i < n; i++) {
			if (len[i] == 0)
				demCL++;
		}



		int demCC = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < len[i]; j++) {
				if (arr[i][j] > i) {

					int x = i;
					int y = arr[i][j];

					visited[x][y] = false;
					visited[y][x] = false;

					for (int k = 0; k < n; k++) {
						dd[k] = 0;
					}

					flag = true;

					BFS(x, y);

					if (flag)
						demCC++;

					visited[x][y] = true;
					visited[y][x] = true;

				}
			}
		}

		cout << demLT << " " << demCL << " " << demCC << endl;
	}
}