Untitled
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; } }