Разъединенный набор (или союз-поиск) | Установите 1 (обнаружение цикла в неориентированном графике)

// Алгоритм поиска объединения для обнаружения цикла в графе
#include <bits/stdc++.h>

using namespace std;

  
// структура для представления ребра в графе

class Edge 

{ 

    public:

    int src, dest; 

}; 

  
// структура для представления графика

class Graph 

{ 

    public:

    // V-> Количество вершин, E-> Количество ребер

    int V, E; 

    // график представлен в виде массива ребер

    Edge* edge; 

}; 

  
// Создаем граф с V вершинами и E ребрами

Graph* createGraph(int V, int E) 

{ 

    Graph* graph = new Graph();

    graph->V = V; 

    graph->E = E; 

    graph->edge = new Edge[graph->E * sizeof(Edge)]; 

    return graph; 

} 

  
// Полезная функция для поиска подмножества элемента i

int find(int parent[], int i) 

{ 

    if (parent[i] == -1) 

        return i; 

    return find(parent, parent[i]); 

} 

  
// Полезная функция для объединения двух подмножеств

void Union(int parent[], int x, int y) 

{ 

    int xset = find(parent, x); 

    int yset = find(parent, y); 

    if(xset != yset)

    { 

        parent[xset] = yset; 

    } 

} 

  
// Основная функция, чтобы проверить, содержит ли данный граф
// цикл или нет

int isCycle( Graph* graph ) 

{ 

    // Выделим память для создания V подмножеств

    int *parent = new int[graph->V * sizeof(int)]; 

    // Инициализируем все подмножества как наборы из одного элемента

    memset(parent, -1, sizeof(int) * graph->V); 

    // Перебирать все ребра графа, найти подмножество обоих

    // вершины каждого ребра, если оба подмножества одинаковы, то

    // в графе есть цикл

    for(int i = 0; i < graph->E; ++i) 

    { 

        int x = find(parent, graph->edge[i].src); 

        int y = find(parent, graph->edge[i].dest); 

        if (x == y) 

            return 1; 

        Union(parent, x, y); 

    } 

    return 0; 

} 

  
// Код драйвера

int main() 

{ 

    / * Давайте создадим следующий график

        0

        | /

        | /

        1 ----- 2 * /

    int V = 3, E = 3; 

    Graph* graph = createGraph(V, E); 

    // добавляем ребро 0-1

    graph->edge[0].src = 0; 

    graph->edge[0].dest = 1; 

    // добавить ребро 1-2

    graph->edge[1].src = 1; 

    graph->edge[1].dest = 2; 

    // добавляем ребро 0-2

    graph->edge[2].src = 0; 

    graph->edge[2].dest = 2; 

    if (isCycle(graph)) 

        cout<<"graph contains cycle"; 

    else

        cout<<"graph doesn't contain cycle"; 

    return 0; 

} 

  
// Этот код предоставлен rathbhupendra

// Алгоритм поиска объединения для обнаружения цикла в графе
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

  
// структура для представления ребра в графе

struct Edge

{

    int src, dest;

};

  
// структура для представления графика

struct Graph

{

    // V-> Количество вершин, E-> Количество ребер

    int V, E;

    // график представлен в виде массива ребер

    struct Edge* edge;

};

  
// Создаем граф с V вершинами и E ребрами

struct Graph* createGraph(int V, int E)

{

    struct Graph* graph = 

           (struct Graph*) malloc( sizeof(struct Graph) );

    graph->V = V;

    graph->E = E;

    graph->edge = 

        (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );

    return graph;

}

  
// Полезная функция для поиска подмножества элемента i

int find(int parent[], int i)

{

    if (parent[i] == -1)

        return i;

    return find(parent, parent[i]);

}

  
// Полезная функция для объединения двух подмножеств

void Union(int parent[], int x, int y)

{

    int xset = find(parent, x);

    int yset = find(parent, y);

    if(xset!=yset){

       parent[xset] = yset;

    }

}

  
// Основная функция, чтобы проверить, содержит ли данный граф
// цикл или нет

int isCycle( struct Graph* graph )

{

    // Выделим память для создания V подмножеств

    int *parent = (int*) malloc( graph->V * sizeof(int) );

    // Инициализируем все подмножества как наборы из одного элемента

    memset(parent, -1, sizeof(int) * graph->V);

    // Перебирать все ребра графа, найти подмножество обоих

    // вершины каждого ребра, если оба подмножества одинаковы, то

    // в графе есть цикл

    for(int i = 0; i < graph->E; ++i)

    {

        int x = find(parent, graph->edge[i].src);

        int y = find(parent, graph->edge[i].dest);

        if (x == y)

            return 1;

        Union(parent, x, y);

    }

    return 0;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    / * Давайте создадим следующий график

         0

        | /

        | /

        1 ----- 2 * /     

    int V = 3, E = 3;

    struct Graph* graph = createGraph(V, E);

    // добавляем ребро 0-1

    graph->edge[0].src = 0;

    graph->edge[0].dest = 1;

    // добавить ребро 1-2

    graph->edge[1].src = 1;

    graph->edge[1].dest = 2;

    // добавляем ребро 0-2

    graph->edge[2].src = 0;

    graph->edge[2].dest = 2;

    if (isCycle(graph))

        printf( "graph contains cycle" );

    else

        printf( "graph doesn't contain cycle" );

    return 0;

}

// Java-программа для алгоритма поиска объединения для обнаружения цикла в графе

import java.util.*;

import java.lang.*;

import java.io.*;

class Graph

{

    int V, E;    // V-> нет. вершин и E-> количество ребер

    Edge edge[]; // / коллекция всех ребер

    class Edge

    {

        int src, dest;

    };

    // Создаем граф с V вершинами и E ребрами

    Graph(int v,int e)

    {

        V = v;

        E = e;

        edge = new Edge[E];

        for (int i=0; i<e; ++i)

            edge[i] = new Edge();

    }

    // Полезная функция для поиска подмножества элемента i

    int find(int parent[], int i)

    {

        if (parent[i] == -1)

            return i;

        return find(parent, parent[i]);

    }

    // Полезная функция для объединения двух подмножеств

    void Union(int parent[], int x, int y)

    {

        int xset = find(parent, x);

        int yset = find(parent, y);

        parent[xset] = yset;

    }

    // Основная функция, чтобы проверить, является ли данный граф

    // содержит цикл или нет

    int isCycle( Graph graph)

    {

        // Выделим память для создания V подмножеств

        int parent[] = new int[graph.V];

        // Инициализируем все подмножества как наборы из одного элемента

        for (int i=0; i<graph.V; ++i)

            parent[i]=-1;

        // Перебирать все ребра графа, найти подмножество обоих

        // вершины каждого ребра, если оба подмножества одинаковы, то

        // в графе есть цикл

        for (int i = 0; i < graph.E; ++i)

        {

            int x = graph.find(parent, graph.edge[i].src);

            int y = graph.find(parent, graph.edge[i].dest);

            if (x == y)

                return 1;

            graph.Union(parent, x, y);

        }

        return 0;

    }

    // Метод драйвера

    public static void main (String[] args)

    {

        / * Давайте создадим следующий график

         0

        | /

        | /

        1 ----- 2 * /

        int V = 3, E = 3;

        Graph graph = new Graph(V, E);

        // добавляем ребро 0-1

        graph.edge[0].src = 0;

        graph.edge[0].dest = 1;

        // добавить ребро 1-2

        graph.edge[1].src = 1;

        graph.edge[1].dest = 2;

        // добавляем ребро 0-2

        graph.edge[2].src = 0;

        graph.edge[2].dest = 2;

        if (graph.isCycle(graph)==1)

            System.out.println( "graph contains cycle" );

        else

            System.out.println( "graph doesn't contain cycle" );

    }

}

# Программа Python для алгоритма union-find для обнаружения цикла в неориентированном графе
# у нас есть один egde для любых двух вершин, то есть 1-2 это либо 1-2, либо 2-1, но не оба

from collections import defaultdict

   
# Этот класс представляет неориентированный граф, используя представление списка смежности

class Graph:

    def __init__(self,vertices):

        self.V= vertices #No. вершин

        self.graph = defaultdict(list) # словарь по умолчанию для хранения графика

    # функция для добавления ребра на график

    def addEdge(self,u,v):

        self.graph[u].append(v)

    # Полезная функция для поиска подмножества элемента i

    def find_parent(self, parent,i):

        if parent[i] == -1:

            return i

        if parent[i]!= -1:

             return self.find_parent(parent,parent[i])

    # Полезная функция для объединения двух подмножеств

    def union(self,parent,x,y):

        x_set = self.find_parent(parent, x)

        y_set = self.find_parent(parent, y)

        parent[x_set] = y_set

    # Основная функция, чтобы проверить, является ли данный граф

    # содержит цикл или нет

    def isCyclic(self):

        # Выделите память для создания V подмножеств и

        # Инициализировать все подмножества как наборы из одного элемента

        parent = [-1]*(self.V)

        # Перебрать все ребра графа, найти подмножество обоих

        # вершин каждого ребра, если оба подмножества одинаковы, то

        # есть цикл в графе.

        for i in self.graph:

            for j in self.graph[i]:

                x = self.find_parent(parent, i) 

                y = self.find_parent(parent, j)

                if x == y:

                    return True

                self.union(parent,x,y)

  
# Создайте график, приведенный на диаграмме выше

g = Graph(3)

g.addEdge(0, 1)

g.addEdge(1, 2)

g.addEdge(2, 0)

if g.isCyclic():

    print "Graph contains cycle"

else :

    print "Graph does not contain cycle "

   
# Этот код предоставлен Ниламом Ядавом