第三题

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";
    }
}

当输入节点数 $n=10^5$，边数 $m=2\times10^5$ 时，程序能否高效运行（ ）。

{{ select(1) }}

• 能，$\Theta(n+m)$ 复杂度
• 不能，$\Theta(nm)$ 复杂度
• 不能，递归栈溢出
• 取决于图的具体结构