DataStructureAndAlgorithm/2023205/main.cpp

#include <stdio.h>
// 并查集。并查集只关注双向连通性。

struct Edge {
    int next;
    unsigned short end;
    bool used_in_dfs;
};

Edge edges[1050000];
char nodes_visited[65540];
int head[65540], len;

int add_edge(int start, int terminal) {
    edges[++len].end = terminal;
    edges[len].next = head[start];
    head[start] = len;
    return 0;
}

int dfs(int start) {
    if (nodes_visited[start] >= 1) {
        // nodes_visited[start] = 2;
        return 0;
    }
    nodes_visited[start] = 1;
    for (int j = head[start]; j != 0; j = edges[j].next) {
        edges[j].used_in_dfs = dfs(edges[j].end);
    }
    return 1;
}

int dfs_with_dead_edge(int start, int dead_edge_start, int dead_edge_end) {
    if (nodes_visited[start] >= 1) {
        return 0;
    }
    nodes_visited[start] = 1;
    if (start == dead_edge_start) {
        for (int j = head[start]; j != 0; j = edges[j].next) {
            if (edges[j].end == dead_edge_end) {
                continue;
            }
            dfs_with_dead_edge(edges[j].end, dead_edge_start, dead_edge_end);
        }
        return 0;
    }

    for (int j = head[start]; j != 0; j = edges[j].next) {
        dfs_with_dead_edge(edges[j].end, dead_edge_start, dead_edge_end);
    }

    return 0;
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    for (int start = 0; start < N; start++) {
        int edge_count;
        scanf("%d", &edge_count);
        for (int j = 0; j < edge_count; j++) {
            int terminal;
            scanf("%d", &terminal);
            add_edge(start, terminal);
        }
    }

    dfs(0);

    for (int i = 0; i < N; i++) {
        if (nodes_visited[i] < 1) {
            // Not connected!
            for (int j = 0; j <= M; j++) {
                printf("0\n");
            }
            return 0;
        }
    }

    printf("1\n");

    // for (int i = 0; i < M; i++) {
    //     int start, end;
    //     scanf("%d %d", &start, &end);
    //     if (nodes_visited[end] == 2) {
    //         printf("1\n");
    //     }
    //     else {
    //         printf("0\n");
    //     }
    // }

    for (int i = 0; i < M; i++) {
        int start, end;
        scanf("%d %d", &start, &end);
        for (int j = head[start]; j != 0; j = edges[j].next) {
            if (edges[j].end == end) {
                if (edges[j].used_in_dfs) {
                    for (int k = 0; k < N; k++) {
                        nodes_visited[k] = 0;
                    }
                    dfs_with_dead_edge(0, start, end);

                    bool connected = true;
                    for (int k = 0; k < N; k++) {
                        if (nodes_visited[k] < 1) {
                            printf("0\n");
                            connected = false;
                            break;
                        }
                    }
                    if (connected) {
                        printf("1\n");
                    } 
                }
                else {
                    printf("1\n");
                }
                break;
            }
        }
    }
    return 0;
}