无向图

指边(edge)无权重，只链接两个结点(node)的线

找还

判断是否有环，有一个基本的准则就是会重复访问已访问的结点，在排除有自环的情况下有三种方法可以判断环的存在。

下列方法统一使用 vis[] 作为访问记录，adj[]做邻接表

一. 深度优先算法(DFS)

bool dfs(int pos, int parent) {
    vis[pos] = true;
    for (auto x: adj[pos]) {
        if (x != parent && vis[x] == true) {
            entry_node = x;
            return true;
        } else if (x != parent) {
            if (dfs(x, pos)) {
                return true;
            }
        }
    }
    return false;
}

重点在于判断邻近的节点是不是父节点

二. 广度优先算法(BFS)

incomplete

bool bfs(int pos) {
    queue<int> access;
    queue<int> parent;
    access.push(pos);
    parent.push(-1);
    vis[pos] = true;
    while (!access.empty()) {
        int now = access.front();
        access.pop();
        int p=parent.front();
        parent.pop();
        if (!vis[now]) {
            vis[now] = true;
        }
        for (auto x: adj[now]) {
            if (vis[x] && x != parent.front()) {
                return true;
            }
            access.push(x);
            parent.push(now);
        }
    }
    return false;
}

三. 并查集(Union Set)

只要当两个建立链接的节点都拥有同一个根节点时，那么便存在环，这种方法下无需考虑自环的情况。

vector<int> parent(n+1,-1); 
int find(int node) {
    if (parent[node] == -1) {
        return node;
    }
    return find(parent[node]);
}

void unite(int node1, int node2) {
    parent[node1] = find(node2);
}

bool is_ring(void) {
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        int x = find(a);
        int y = find(b);
        cout << x << ' ' << y << endl;
        if (x == a) {
            parent[a] = b;
        } else if (y == b) {
            parent[b] = a;
        } else if (find(a) == find(b)) {
            parent[find(a)] = find(b);
            return true;
        }
    }
    return false;
}