c++ - 我的代码中查找图表是否为二分图有什么问题？

Question

我正在做一个简单的 BFS 并标记当前遍历顶点下的顶点的相邻元素，如果在当前遍历顶点的下一个顶点中再次找到它，那么它不是二分的。

#include <bits/stdc++.h>

using namespace std;

vector<long> g[100000];

void neighbour(long it, vector<bool>& nei)
{
    for (auto itr : g[it])
        nei[itr] = true;
}

bool BFSbipartile(vector<bool>& vis, long v, long ver)
{
    queue<long> q;

    bool flag = true;
    q.push(v);
    vis[v] = true;
    while (!q.empty()) {
        long t = q.front();
        q.pop();
        vector<bool> nei(ver + 1, false);
        for (auto it : g[t]) {
            if (!vis[it]) {
                neighbour(it, nei);
                if (nei[it] == true) {
                    flag = false;
                    break;
                }
                vis[it] = true;
                q.push(it);
            }
            if (!flag)
                return false;
        }
    }
    return true;
}

int main()
{
    long v, e, e1, e2;
    cin >> v >> e;
    for (long i = 0; i < e; i++) {
        cin >> e1 >> e2;
        g[e1].push_back(e2);
        g[e2].push_back(e1);
    }
    vector<bool> vis(v + 1, false);
    bool tru = true;
    for (int i = 1; i <= v; i++) {
        if (!vis[i])
            tru = BFSbipartile(vis, i, v);
        if (!tru) {
            cout << 0 << endl;
            break;
        }
    }
    if (tru)
        cout << 1 << endl;

    return 0;
}

标签： c++algorithmdata-structuresgraphbreadth-first-search