<jupyter_start><jupyter_text>Union Find Cycle detectionTo detect the presence of cycles in a graph.This method assumes that the graph doesn’t contain any self-loops.<jupyter_code>def find_Parent(node, parent) :
    # -1 indicates that there is a self loop for that node.
    if parent[node] == -1 :
        return node
    else :
        return find_Parent(parent[node], parent)
    return

def union(parent, x, y) :
    x_set = find_Parent(x, parent)
    y_set = find_Parent(y, parent)
    parent[x_set] = y_set
    return

def check_Cyclic(graph) :
    parent = {}
    for v in graph :
        parent[v] = -1
    for u in graph :
        for v in graph[u] :
            x = find_Parent(u, parent)
            y = find_Parent(v, parent)
            if x == y :
                return True
            union(parent, x, y)
    return False

def get_Input() :
    graph = {}
    n = int(input('Enter the number of nodes in the graph :- '))
    for i in range(n) :
        name = input('Enter the name of the node :- ')
        s = input('Enter all the adjascent nodes to this node seperated by a space :-')
        if s == '' :
            graph[name] = []
        else :
            adj = list(s.split(' '))
            graph[name] = adj
    return graph

graph = get_Input()
#graph = graph_1
if check_Cyclic(graph) :
    print('The graph contains a cycle.')
else :
    print('The graph contains no cycle.')<jupyter_output>The graph contains a cycle.<jupyter_text>Using Union by rank and Path Compression<jupyter_code>class Nodes :
    def __init__(self, parent, rank) :
        self.parent = parent
        self.rank = rank
        return

def get_Input() :
    graph = {}
    n = int(input('Enter the number of nodes in the graph :- '))
    for i in range(n) :
        name = input('Enter the name of the node :- ')
        s = input('Enter all the adjascent nodes to this node seperated by a space :-')
        if s == '' :
            graph[name] = []
        else :
            adj = list(s.split(' '))
            graph[name] = adj
    return graph

def find(nodeSet, node) :
    if nodeSet[node].parent != node :
        nodeSet[node].parent = find(nodeSet, nodeSet[node].parent)
    return nodeSet[node].parent

def union(nodeSet, x, y) :
    # To attach the tree with a smaller rank with the one with a larger rank.
    if nodeSet[x].rank > nodeSet[y].rank :
        nodeSet[y].parent = x
    elif nodeSet[y].rank > nodeSet[x].rank :
        nodeSet[x].parent = y
    else :
        nodeSet[x].parent = y
        nodeSet[y].rank += 1
    return

def detect_Cycle(graph) :
    nodeSet = {}
    for v in graph :
        nodeSet[v] = Nodes(v, 0)
    for u in graph :
        x = find(nodeSet, u)
        for v in graph[u] :
            y = find(nodeSet, v)
            if x == y :
                return True
            else :
                union(nodeSet, x, y)
    return False

graph = get_Input()
#graph = graph_4
if detect_Cycle(graph) :
    print('A Cycle exists in the graph.')
else :
    print('No Cycle exists in the graph.')<jupyter_output>No Cycle exists in the graph.<jupyter_text>Sample Inputs<jupyter_code>graph_1 = {1 : [2],
           2 : [3],
           3 : [1]}

graph_2 = {1 : [2],
           2 : [3],
           3 : []}

graph_3 = {1 : [2, 3],
           2 : [3],
           3 : []}

graph_4 = {0: [3, 2],
           1: [],
           2: [3],
           3: []}<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11940298507462686, 'fraction_numerical': 0.010242903131401814, 'mean_word_length': 1.9747606614447346, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '277414', 'license': 'MIT', 'n_tokens_mistral': 1132, 'n_tokens_neox': 1109, 'n_words': 353, 'path': 'Data-Structures/Graph/Union-Find/UnionFindCycleDetection.ipynb', 'repo_name': 'aadhityasw/Data-Structures-Algorithms', 'size': '3417'}