【算法集训】基础数据结构：十二、邻接表

今天的两道题都有难度，第一道勉强能懂，第二道后面再二刷吧

第一题 841. 钥匙和房间

int visited[1010]; //访问数组,决定该房间是否被访问过;

void dfs(int u, int** rooms, int r, int * c) {
    if(visited[u]) {
        return;
    }
    visited[u] = 1;
    for(int i = 0; i < c[u]; ++i) {
        dfs(rooms[u][i], rooms, r, c);
    }
}

bool canVisitAllRooms(int** rooms, int roomsSize, int* roomsColSize) {
    memset(visited, 0, sizeof(visited));
    int r = roomsSize;
    dfs(0, rooms, r, roomsColSize); //计算出从0号房间开始所有访问过的房间,记录到visited中
    for(int i = 0; i < r; ++i) {
        if(visited[i] == 0) {
            return false;
        }
    }
    return true;
}

第二题 面试题 04.01. 节点间通路

struct LinkedNode {
    int data;
    struct LinkedNode * next;
};

struct LinkedNode * head[100001];  
int front, tail, q[200001];
int visited[200001];

bool findWhetherExistsPath(int n, int** graph, int graphSize, int* graphColSize, int start, int target){
    //初始化节点
    for(int i = 0; i < n; ++i) {
        head[i] = (struct LinkedNode *)malloc(sizeof(struct LinkedNode));
        head[i]->next = NULL;
    }

    for(int i = 0; i < graphSize; ++i) {
        int s = graph[i][0]; //取开始数
        int t = graph[i][1]; //取目标数
        struct LinkedNode * temp = (struct LinkedNode *)malloc(sizeof(struct LinkedNode));
        temp->data = t;
        temp->next = head[s]->next;
        head[s]->next = temp;
    }

    front = tail = 0;
    q[tail++] = start;
    memset(visited, 0, sizeof(visited));
    visited[start] = 1;
    while(front < tail) {
        int now = q[front++];
        if(now == target) {
            return true;
        }
        for(struct LinkedNode * tmp = head[now]->next; tmp; tmp = tmp->next) {
            int v = tmp->data;
            if(!visited[v]) {
                visited[v] = 1;
                q[tail++] = v;
            }
        }
    }
    return false;
}