Input

2
4
0 1 1 1 
1 0 1 1 
1 1 0 1 
1 1 1 0 
7
0 1 0 0 0 0 0 
0 0 1 1 0 0 0 
1 0 0 0 0 0 0 
1 0 1 0 0 0 0 
0 0 0 0 0 1 1 
0 1 0 0 0 0 0 
0 0 0 1 0 1 0 

Output

Yes
No

Bài toán này yêu cầu kiểm tra xem một đồ thị có hướng có phải là đồ thị liên thông không. Để làm điều này, chúng ta có thể sử dụng thuật toán DFS hoặc BFS. Trong ví dụ này, tôi sử dụng DFS.

Để xác định xem đồ thị có phải là đồ thị liên thông mạnh (tức là mọi cặp đỉnh đều có thể đến được nhau), chúng ta cần thực hiện DFS bắt đầu từ mỗi đỉnh và kiểm tra xem có thể truy cập được đến mọi đỉnh khác không.

Hai phần quan trọng trong mã nguồn:

• DFS: Hàm này thực hiện duyệt sâu từ một đỉnh đã chỉ định và đánh dấu các đỉnh đã truy cập được.

• Kiểm tra liên thông: Hàm này kiểm tra xem từ mỗi đỉnh bắt đầu, có thể truy cập được đến mọi đỉnh khác không.

Mã nguồn đầy đủ:

#include <iostream>
using namespace std;
const int maxn = 1e3 + 10;
int graph[maxn][maxn]; // Ma trận kề
int visited[maxn]; // Mảng đánh dấu các đỉnh đã truy cập
int numVertices;
int testCases;

void dfs(int currentVertex, int numVertices) {
    visited[currentVertex] = 1; // Đánh dấu đỉnh hiện tại đã được truy cập
    for (int nextVertex = 0; nextVertex < numVertices; nextVertex++) {
        // Kiểm tra xem có một cạnh từ đỉnh hiện tại đến đỉnh tiếp theo và đỉnh tiếp theo chưa được truy cập
        if (graph[currentVertex][nextVertex] == 1 && visited[nextVertex] == 0) {
            dfs(nextVertex, numVertices); // Duyệt tiếp từ đỉnh tiếp theo
        }
    }
}

bool isStronglyConnected(int numVertices) {
    // Thực hiện DFS từ mỗi đỉnh và kiểm tra xem có thể truy cập được đến mọi đỉnh khác
    for (int startVertex = 0; startVertex < numVertices; startVertex++) {
        // Đặt lại mảng visited để bắt đầu từ đỉnh mới
        for (int i = 0; i < numVertices; i++) {
            visited[i] = 0;
        }
        dfs(startVertex, numVertices); // Bắt đầu DFS từ đỉnh startVertex
        // Kiểm tra xem có đỉnh nào không được truy cập không
        for (int i = 0; i < numVertices; i++) {
            if (visited[i] == 0) {
                return false; // Đồ thị không liên thông mạnh
            }
        }
    }
    return true; // Đồ thị là liên thông mạnh
}

int main() {
    cin >> testCases;
    while (testCases-- > 0) {
        cin >> numVertices;
        // Khởi tạo ma trận kề và mảng visited
        for (int i = 0; i < numVertices; i++) {
            visited[i] = 0;
            for (int j = 0; j < numVertices; j++) {
                graph[i][j] = 0;
            }
        }
        // Đọc ma trận kề
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                cin >> graph[i][j];
            }
        }
        bool result = isStronglyConnected(numVertices); // Kiểm tra liên thông mạnh
        if (result) {
            cout << "Yes" << endl; // Đồ thị là liên thông mạnh
        } else {
            cout << "No" << endl; // Đồ thị không là liên thông mạnh
        }
    }
}