1004: Xi and Bo

#include<iostream>

using namespace std;

/*
解题思路：
利用图的深度优先遍历检查是否有从起点到终点的路径。
使用邻接表保存整个图。图为无向图
设置一个变量保存已经访问过的节点，考虑到只有一百个节点（车站），所以使用一个长度为100的数组来保存每个节点的访问状态。
*/

int BFS(int map[100][100], int*& visited, int start, int end) {
    //检查当前节点是否已访问过
    if (visited[start] == 1) {
        return -1;
    }
    //标记当前节点为已访问
    visited[start] = 1;

    //遍历当前节点的邻接节点
    int index = 0;
    while (map[start][index] != -1){
        if (map[start][index] == end || BFS(map, visited, map[start][index], end) == 1) {
            return 1;
        }
        index++;
    }

    //当前节点没有到终点的路径
    return 0;
}

int main() {
    int t;
    cin >> t;
    int* results = new int[t];

    for (int i = 0; i < t; i++) {
        //图
        int map[100][100];
        for (int k = 0; k < 100; k++) {
            for (int m = 0; m < 100; m++) {
                map[k][m] = -1;
            }
        }

        int start, end;
        cin >> start >> end;

        int n;
        cin >> n;
        for (int k = 0; k < n; k++) {
            int route_len;
            cin >> route_len;

            int pre, later;
            cin >> pre;
            for (int m = 1; m < route_len; m++) {
                cin >> later;
                int index_pre = 0;
                while (map[pre][index_pre] != -1){
                    index_pre++;
                }
                map[pre][index_pre] = later;
                int index_later = 0;
                while (map[later][index_later] != -1) {
                    index_later++;
                }
                map[later][index_later] = pre;
                
                pre = later;
            }
        }

        int* visted = new int[100];
        results[i] = BFS(map, visted, start, end);
        
        delete[] visted;
    }

    for (int i = 0; i < t; i++) {
        cout << (results[i] == 0 ? "No" : "Yes") << endl;
    }

    delete[] results;
}