Блог

Я написал код, чтобы проверить, является ли данный граф двудольным или нет, но не уверен, почему один код работает, а другой нет.

Нижеприведенное не работает,

 bool dfs(int i, int color, vector<vector<int>> amp;graph) {
    if (visited[i] == -1) {
        visited[i] = color;
        for (int adj: graph[i])
            return dfs(adj, !color, graph);
    }
    return (visited[i] == color);
}
bool isBipartite(vector<vector<int>> amp;graph) {
    visited.assign(105, -1);
    for (int i = 0; i < graph.size(); i  ) {
        if (visited[i] == -1)
            if (!dfs(i, 0, graph)) return false;
    }
    return true;
}
vector<int> visited;
 

Но когда я изменюсь выше на это

 bool dfs(int i, int color, vector<vector<int>> amp;graph) {
    if (visited[i] == -1) {
        visited[i] = color;
        for (int adj: graph[i])
            if (!dfs(adj, !color, graph)) {
                return false;
            }
    }
    return (visited[i] == color);

}
bool isBipartite(vector<vector<int>> amp;graph) {
    visited.assign(105, -1);
    for (int i = 0; i < graph.size(); i  ) {
        if (visited[i] == -1)
            if (!dfs(i, 0, graph)) return false;
    }
    return true;
}
vector<int> visited;
 

это работает, кто-нибудь может сказать, почему ? Обратите внимание, что изменились только строки 5-я и 6-я в функции dfs.

не должны ли оба кода работать, так как они, похоже, работают одинаково ?

В вашем первом фрагменте кода,

         for (int adj: graph[i])
            return dfs(adj, !color, graph);
 

что происходит, так это то, что вы возвращаетесь в течение первой итерации цикла for. Таким образом, для каждого узла вы проверяете только одного из его соседей и игнорируете остальные.

Обратите внимание, что ваш второй фрагмент также не совсем корректен. Вы упускаете случай, когда у узла нет соседей или все его соседи имеют правильные цвета:

 bool dfs(int i, int color, vector<vector<int>> amp;graph) {
    if (visited[i] == -1) {
        visited[i] = color;
        for (int adj: graph[i])
            if (!dfs(adj, !color, graph)) {
                return false;
            }
        return true;
    }
    return (visited[i] == color);
}