第三题

bool valid = true;

std::vector<int> adj[max_node];
bool instack[max_node] = {false};
bool visited[max_node] = {false};

void dfs(int node)
{
    instack[node] = true;
    visited[node] = true;
    for (auto after : adj[node]) {
        if (!visited[after]) {
            visited[after] = true;
            dfs(after);
        }
        else if (instack[after]) {
            valid = false;
        }
    }
    instack[node] = false;
}

int main()
{
    int n, m;
    std::cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        std::cin >> x >> y;
        adj[x].push_back(y);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!visited[i])
        {
            dfs(i);
        }
    }
    if (valid) {
        std::cout << "Valid\n";
    } else {
        std::cout << "Invalid\n";
    }
}

若图有多个连通分量，程序能正确检测所有连通分量中的环。

{{ select(1) }}

• 正确
• 错误