提出 #41971216

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

bool is_good_graph(int N, int M, const vector<pair<int, int>>& edges, int K, const vector<pair<int, int>>& forbidden_paths, int Q, const vector<pair<int, int>>& queries) {
    vector<vector<int>> graph(N + 1);
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    unordered_set<int> forbiddenSet;
    for (const auto& path : forbidden_paths) {
        int x = path.first;
        int y = path.second;
        forbiddenSet.insert(x * N + y);  // Encode the path as a unique number
        forbiddenSet.insert(y * N + x);
    }

    vector<bool> visited(N + 1, false);

    bool is_good;
    for (const auto& query : queries) {
        int p = query.first;
        int q = query.second;

        // Add the new edge to the graph
        graph[p].push_back(q);
        graph[q].push_back(p);

        is_good = true;

        // Check if any forbidden path exists in the modified graph
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                dfs(graph, forbiddenSet, visited, i, -1, is_good);
            }
            if (!is_good) {
                break;
            }
        }

        // Remove the new edge from the graph
        graph[p].pop_back();
        graph[q].pop_back();

        // Output the result
        cout << (is_good ? "Yes" : "No") << endl;
    }
}

void dfs(const vector<vector<int>>& graph, const unordered_set<int>& forbiddenSet, vector<bool>& visited, int node, int parent, bool& is_good) {
    visited[node] = true;

    for (int neighbor : graph[node]) {
        if (neighbor == parent) {
            continue;
        }
        if (visited[neighbor]) {
            continue;
        }

        if (forbiddenSet.count(node * graph.size() + neighbor)) {
            is_good = false;
            return;
        }

        dfs(graph, forbiddenSet, visited, neighbor, node, is_good);
        if (!is_good) {
            return;
        }
    }
}

int main() {
    int N, M, K, Q;
    cin >> N >> M;

    vector<pair<int, int>> edges(M);
    for (int i = 0; i < M; i++) {
        cin >> edges[i].first >> edges[i].second;
    }

    cin >> K;

    vector<pair<int, int>> forbidden_paths(K);
    for (int i = 0; i < K; i++) {
        cin >> forbidden_paths[i].first >> forbidden_paths[i].second;
    }

    cin >> Q;

    vector<pair<int, int>> queries(Q);
    for (int i = 0; i < Q; i++) {
        cin >> queries[i].first >> queries[i].second;
    }

    is_good_graph(N, M, edges, K, forbidden_paths, Q, queries);

    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘bool is_good_graph(int, int, const std::vector<std::pair<int, int> >&, int, const std::vector<std::pair<int, int> >&, int, const std::vector<std::pair<int, int> >&)’:
./Main.cpp:40:17: error: ‘dfs’ was not declared in this scope
   40 |                 dfs(graph, forbiddenSet, visited, i, -1, is_good);
      |                 ^~~
./Main.cpp:54:1: warning: no return statement in function returning non-void [-Wreturn-type]
   54 | }
      | ^
./Main.cpp:7:31: warning: unused parameter ‘M’ [-Wunused-parameter]
    7 | bool is_good_graph(int N, int M, const vector<pair<int, int>>& edges, int K, const vector<pair<int, int>>& forbidden_paths, int Q, const vector<pair<int, int>>& queries) {
      |                           ~~~~^
./Main.cpp:7:75: warning: unused parameter ‘K’ [-Wunused-parameter]
    7 | bool is_good_graph(int N, int M, const vector<pair<int, int>>& edges, int K, const vector<pair<int, int>>& forbidden_paths, int Q, const vector<pair<int, int>>& queries) {
      |                                                                       ~~~~^
./Main.cpp:7:129: warning: unused parameter ‘Q’ [-Wunused-parameter]
    7 | bool is_good_graph(int N, int M, const vector<pair<int, int>>& edges, int K, const vector<pair<int, int>>& forbidden_paths, int Q, const vector<pair<int, int>>& queries) {
      |                                                                                                                             ~~~~^