Comment vérifier si un cycle non orienté est formé en fonction d'un ensemble d'arêtes et quelle est sa complexité?

Question

On m'a donné seulement un ensemble d'arêtes et on m'a demandé s'il y avait un cycle dans le graphique (le graphique peut ne pas être connecté). Je sais qu'il peut être facilement résolu en utilisant un simple DFS. Mais je voudrais savoir s'il existe une autre méthode avec une complexité réduite car je peux recevoir plusieurs requêtes de ce type pour vérifier les cycles et exécuter dfs chaque fois donnerait O (nq) complexité, n nombre d'arêtes et q nombre de requêtes.

Answer 1

Vous pouvez utiliser disjoints, il peut trouver tous les cycles O(E) (E est le nombre d'arêtes)

Ce qu'il fait:

1. garde la trace des noeuds sont reliés, directement ou indirectement (Cela signifie que les deux nœuds sont dans le même jeu).

2. Mettez deux nœuds dans le même ensemble. (Ce qui signifie qu'ils sont connectés). En fait, il s'agit d'une union des deux ensembles de ces nœuds.

ensemble disjoint fait ces deux opérations O(1). Voilà comment je mets en œuvre avec disjoints set compression de chemin:

#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: Mise en place du même bord plusieurs fois seront comptés comme un cycle.