在给定的一组边的情况下，如何检查无向循环是否形成？其复杂度是多少？

本文介绍了在给定的一组边的情况下，如何检查无向循环是否形成？其复杂度是多少？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

仅给了我一组边缘，并询问图形中是否存在循环（图形可能未连接）。我知道可以使用简单的DFS轻松解决它。但是我想知道是否还有其他方法可以降低复杂度，因为我可能会收到多个这样的查询来检查周期，并且每次运行dfs都会带来O（nq）复杂度，n个边数和q个查询。 / p>

I have been given only a set of edges and asked if there is a cycle in the graph (graph may not be connected). I know it can be easily solved using a simple DFS. But I would like to know if there is any other method with reduced complexity as I may receive multiple such queries to check for cycles and running dfs every time would give O(nq) complexity, n number of edges and q number of queries.

推荐答案

可以使用不交集，它可以在 O（E）（E是边数）

You can use Disjoint sets, It can find all cycles in O(E) (E is number of edges)

功能：

 
  跟踪直接或间接连接的节点
（意味着两个节点位于同一集合中）。

Keeps track of which nodes are connected, directly or indirectly(Meaning the two nodes are in the same set).

放置同一集合中的两个节点。（意味着它们连接了）。实际上，它对这两个节点来自的两个集合进行并集。

Put two nodes in the same set. (Meaning they areconnected). Actually, it does a union of the two sets these nodes are from.

不相交集在这两个操作中都完成了 O（1）。这是我如何使用路径压缩来实现不相交集：

Disjoint set does both of these operations in O(1).Here's how I implement Disjoint set with path compression:

#include <iostream>
#include <cstdio>

using namespace std;

// This array is used to represent a backward tree (Forest actually)
// all nodes part of a tree are in the same set
int disjointset[1000];

// at first all nodes are separated
// that is they are part of a 1 element set
void initialize(int n){
    for(int i= 0; i<=n; i++){
        disjointset[i]= i;
    }
}

// get the root parent of node a in disjoint tree structure
int getParent(int a){
    if(disjointset[a] == a)
        return a;

    // we do this assignment to shorten the path from this node to it's top ancestor in tree
    // this is called path compression
    disjointset[a] = getParent(disjointset[a]);

    return disjointset[a];
}

// check if two nodes are directly/indirectly connected
bool connected(int a, int b){
    return getParent(a) == getParent(b);
}

// join two nodes a and b, after this they will be connected
void join(int a, int b){
    disjointset[getParent(a)] = getParent(b);
}

int main(){
    //freopen("F:/input.txt", "r", stdin);

    // n nodes, e edges
    int n, e, u, v;

    cin>>n>>e;   // e number of edges

    //initialize the backward tree of disjoint set
    initialize(n);

    for(int i= 0; i<e; i++){
        cin>>u>>v;

        if(connected(u, v)){
            cout<< "Cycle found"<<endl;
        }

        join(u,v);
    }

}


/*

//sample input
//6 nodes 6 edges
6 6
1 2
2 3
1 3
3 4
3 5
4 6

*/

注意：多次插入同一条边线将被视为一个循环。

Note: Inserting the same edge multiple times will be counted as a cycle.

                        这篇关于在给定的一组边的情况下，如何检查无向循环是否形成？其复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

Set