Posted on by Kalkicode
Code Graph

Check if removing a given edge disconnects a graph

The problem you're addressing is about determining whether removing a given edge from a graph will cause the graph to become disconnected. A disconnected graph is one where there is no path between at least two vertices. Your goal is to create a program that checks whether removing a specific edge disconnects the graph.

Problem Statement and Example

Given a graph with vertices and edges, you need to determine if removing a particular edge will result in the graph becoming disconnected. For example, consider the following graph:

Vertices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Edges: (0,1), (0,3), (0,4), (1,2), (1,5), (2,3), (2,6), (3,4), (3,9), (6,7), (6,8), (9,10), (9,11), (10,11)

You're required to check whether removing a specific edge disconnects the graph. The program should print whether removing the edge will result in the graph being disconnected or not.

Idea to Solve

Example disconnecting graph by edges

To solve this problem, you need to perform a Depth-First Search (DFS) to traverse the graph and determine if all vertices can still be visited after removing the given edge. You can do this by temporarily removing the edge, checking if the graph remains connected, and then adding the edge back.

Pseudocode

function dfs(visited, start)
    mark start as visited
    for each neighbor of start
        if neighbor is not visited
            dfs(visited, neighbor)

function removeNodeEdge(u, v)
    if edge (u, v) doesn't exist
        return false
    remove edge (u, v)
    remove edge (v, u)
    return true

function disconnectByEdge(u, v)
    initialize visited array
    mark all vertices as not visited
    perform dfs(visited, 0)
    if all vertices are visited
        if removeNodeEdge(u, v) is true
            perform dfs(visited, 0)
            if all vertices are visited
                add back edge (u, v)
                print "Remove edge [u-v] not disconnecting this graph"
            else
                print "Remove edge [u-v] disconnecting this graph"
        else
            print "No edge between vertices [u-v]"
    else
        print "Graph is already disconnected"

Algorithm Explanation

  1. The dfs function marks vertices as visited using Depth-First Search.
  2. The removeNodeEdge function removes a given edge between vertices u and v.
  3. The disconnectByEdge function performs the following steps:
    • Initialize the visited array.
    • Perform DFS starting from vertex 0.
    • If all vertices are visited, check if removing the edge (u, v) disconnects the graph.
    • If removing the edge disconnects the graph, print accordingly.
    • If removing the edge doesn't disconnect the graph, add the edge back and print accordingly.
    • If some vertices are not visited, print "Graph is already disconnected".

Code Solution

import java.util.ArrayList;
/*
    Java Program
    Check if removing a given edge disconnects a graph
*/
public class Graph
{
    // Number of vertices in graph
    public int vertices;
    // Use to collect edges information
    public ArrayList < ArrayList < Integer >> adjacencylist;
    public Graph(int vertices)
    {
        this.vertices = vertices;
        this.adjacencylist = new ArrayList < ArrayList < Integer >> (vertices);
        for (int i = 0; i < this.vertices; ++i)
        {
            this.adjacencylist.add(new ArrayList < Integer > ());
        }
    }
    public void addEdge(int u, int v)
    {
        if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
        {
            return;
        }
        // Add node edge
        adjacencylist.get(u).add(v);
        adjacencylist.get(v).add(u);
    }
    // Display graph nodes and edges
    public void printGraph()
    {
        System.out.print("\n Graph Adjacency List ");
        for (int i = 0; i < this.vertices; ++i)
        {
            System.out.print(" \n [" + i + "] :");
            // iterate edges of i node
            for (int j = 0; j < this.adjacencylist.get(i).size(); j++)
            {
                System.out.print("  " + this.adjacencylist.get(i).get(j));
            }
        }
    }
    public void dfs(boolean[] visited, int start)
    {
        if (start < 0 || start >= this.vertices)
        {
            // In case given invalid node
            return;
        }
        // Mark a current visited node
        visited[start] = true;

        int i = 0;
        // Execute edges of given start vertices
        while (i < adjacencylist.get(start).size())
        {
            if (visited[adjacencylist.get(start).get(i)] == false)
            {
                // When edge node not visiting, then perform DFS operation
                dfs(visited, adjacencylist.get(start).get(i));
            }
            // Visit to next node
            i++;
        }
    }

    public int edgePosition(int u, int v)
    {

        int i = 0;
        while(i < this.adjacencylist.get(u).size())
        {
            if(this.adjacencylist.get(u).get(i)==v)
            {
                return i;
            }
            i++;
        }
        return -1;
    }   

    public boolean removeNodeEdge(int u, int v)
    {

        if(u < 0 || v < 0 || u > this.vertices 
            || v > this.vertices )
        {
            return false;
        }
        int a = edgePosition(u,v);
        int b = edgePosition(v,u);

        if(a==-1 || b == -1)
        {
            // Given edge are not exist between given nodes 
            return false;
        }
        // Remove edges
        this.adjacencylist.get(u).remove(a);
        this.adjacencylist.get(v).remove(b);

        return true;

    }
    public void unsetVisit(boolean[] visited)
    {
        for (int i = 0; i < this.vertices; ++i)
        {
            visited[i] = false;
        }
    }
    public boolean isAllVerticesVisit(boolean[] visited)
    {
        for (int i = 0; i < this.vertices; ++i)
        {
            if(visited[i]==false)
            {
                return false;
            }
        }
        return true;
    }
    public void disconnectByEdge(int u, int v)
    {


        boolean[] visited = new boolean[this.vertices];
     
        unsetVisit(visited);

        dfs(visited, 0);

   

        if(isAllVerticesVisit(visited)==true)
        {

            if(removeNodeEdge(u,v)==true)
            {
               
                unsetVisit(visited);

                dfs(visited, 0);

                // Add remove edge
                addEdge(u,v); 

                if(isAllVerticesVisit(visited))
                {
                    // not a bridge edge
                    // graph are not disconnect
          
                    System.out.print("\n Remove edge ["+u+"-"+v+"] not disconnecting this graph ");
                }
                else
                {
             
                    System.out.print("\n Remove edge ["+u+"-"+v+"] disconnecting this graph ");
                }
               
            }
            else
            {
                // When edges are not exist
                System.out.print("\n No edge between vertices ["+u+"-"+v+"]");
            }
        }
        else
        {
            // When graph is already disconnected?
              System.out.print("\n Graph is already disconnected");
        }
     
    }
    public static void main(String[] args)
    {
        Graph graph = new Graph(12);
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 5);
        graph.addEdge(2, 3);
        graph.addEdge(2, 6);
        graph.addEdge(3, 4);
        graph.addEdge(3, 9);
        graph.addEdge(6, 7);
        graph.addEdge(6, 8);
        graph.addEdge(9, 10);
        graph.addEdge(9, 11);
        graph.addEdge(10, 11);
        // Display graph element
        graph.printGraph();

        // Test case
        graph.disconnectByEdge(4,7);
        graph.disconnectByEdge(3,9);
        graph.disconnectByEdge(1,2);
        graph.disconnectByEdge(6,2);
        graph.disconnectByEdge(10,11);

    }
}

input

 Graph Adjacency List
 [0] :  1  3  4
 [1] :  0  2  5
 [2] :  1  3  6
 [3] :  0  2  4  9
 [4] :  0  3
 [5] :  1
 [6] :  2  7  8
 [7] :  6
 [8] :  6
 [9] :  3  10  11
 [10] :  9  11
 [11] :  9  10
 No edge between vertices [4-7]
 Remove edge [3-9] disconnecting this graph
 Remove edge [1-2] not disconnecting this graph
 Remove edge [6-2] disconnecting this graph
 Remove edge [10-11] not disconnecting this graph
// Include header file
#include <iostream>
#include <vector>

using namespace std;
/*
    C++ Program
    Check if removing a given edge disconnects a graph
*/
class Graph
{
	public:
	// Number of vertices in graph
	int vertices;
	// Use to collect edges information
	vector < vector < int > > adjacencylist;
	Graph(int vertices)
	{
		this->vertices = vertices;
		for (int i = 0; i < this->vertices; ++i)
		{
			this->adjacencylist.push_back( vector < int > ());
		}
	}
	void addEdge(int u, int v)
	{
		if (u < 0 || u >= this->vertices || v < 0 || v >= this->vertices)
		{
			return;
		}
		// Add node edge
		this->adjacencylist.at(u).push_back(v);
		this->adjacencylist.at(v).push_back(u);
	}
	// Display graph nodes and edges
	void printGraph()
	{
		cout << "\n Graph Adjacency List ";
		for (int i = 0; i < this->vertices; ++i)
		{
			cout << " \n [" << i << "] :";
			// iterate edges of i node
			for (int j = 0; j < this->adjacencylist.at(i).size(); j++)
			{
				cout << "  " << this->adjacencylist.at(i).at(j);
			}
		}
	}
	void dfs(bool visited[], int start)
	{
		if (start < 0 || start >= this->vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited[start] = true;
		int i = 0;
		// Execute edges of given start vertices
		while (i < this->adjacencylist.at(start).size())
		{
			if (visited[this->adjacencylist.at(start).at(i)] == false)
			{
				// When edge node not visiting, then perform DFS operation
				this->dfs(visited, this->adjacencylist.at(start).at(i));
			}
			// Visit to next node
			i++;
		}
	}
	int edgePosition(int u, int v)
	{
		int i = 0;
		while (i < this->adjacencylist.at(u).size())
		{
			if (this->adjacencylist.at(u).at(i) == v)
			{
				return i;
			}
			i++;
		}
		return -1;
	}
	bool removeNodeEdge(int u, int v)
	{
		if (u < 0 || v < 0 || u > this->vertices || v > this->vertices)
		{
			return false;
		}
		int a = this->edgePosition(u, v);
		int b = this->edgePosition(v, u);
		if (a == -1 || b == -1)
		{
			// Given edge are not exist between given nodes 
			return false;
		}
		// Remove edges
		this->adjacencylist.at(u).erase(this->adjacencylist.at(u).begin() + a);
		this->adjacencylist.at(v).erase(this->adjacencylist.at(v).begin() + b);
		return true;
	}
	void unsetVisit(bool visited[])
	{
		for (int i = 0; i < this->vertices; ++i)
		{
			visited[i] = false;
		}
	}
	bool isAllVerticesVisit(bool visited[])
	{
		for (int i = 0; i < this->vertices; ++i)
		{
			if (visited[i] == false)
			{
				return false;
			}
		}
		return true;
	}
	void disconnectByEdge(int u, int v)
	{
		bool visited[this->vertices];
		this->unsetVisit(visited);
		this->dfs(visited, 0);
		if (this->isAllVerticesVisit(visited) == true)
		{
			if (this->removeNodeEdge(u, v) == true)
			{
				this->unsetVisit(visited);
				this->dfs(visited, 0);
				// Add remove edge
				this->addEdge(u, v);
				if (this->isAllVerticesVisit(visited))
				{
					// not a bridge edge
					// graph are not disconnect
					cout << "\n Remove edge [" << u << "-" 
                  		 << v << "] not disconnecting this graph ";
				}
				else
				{
					cout << "\n Remove edge [" << u << "-" 
                  		 << v << "] disconnecting this graph ";
				}
			}
			else
			{
				// When edges are not exist
				cout << "\n No edge between vertices [" << u << "-" 
              											<< v << "]";
			}
		}
		else
		{
			// When graph is already disconnected?
			cout << "\n Graph is already disconnected";
		}
	}
};
int main()
{
	Graph *graph = new Graph(12);
	graph->addEdge(0, 1);
	graph->addEdge(0, 3);
	graph->addEdge(0, 4);
	graph->addEdge(1, 2);
	graph->addEdge(1, 5);
	graph->addEdge(2, 3);
	graph->addEdge(2, 6);
	graph->addEdge(3, 4);
	graph->addEdge(3, 9);
	graph->addEdge(6, 7);
	graph->addEdge(6, 8);
	graph->addEdge(9, 10);
	graph->addEdge(9, 11);
	graph->addEdge(10, 11);
	// Display graph element
	graph->printGraph();
	// Test case
	graph->disconnectByEdge(4, 7);
	graph->disconnectByEdge(3, 9);
	graph->disconnectByEdge(1, 2);
	graph->disconnectByEdge(6, 2);
	graph->disconnectByEdge(10, 11);
	return 0;
}

input

 Graph Adjacency List
 [0] :  1  3  4
 [1] :  0  2  5
 [2] :  1  3  6
 [3] :  0  2  4  9
 [4] :  0  3
 [5] :  1
 [6] :  2  7  8
 [7] :  6
 [8] :  6
 [9] :  3  10  11
 [10] :  9  11
 [11] :  9  10
 No edge between vertices [4-7]
 Remove edge [3-9] disconnecting this graph
 Remove edge [1-2] not disconnecting this graph
 Remove edge [6-2] disconnecting this graph
 Remove edge [10-11] not disconnecting this graph
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program
    Check if removing a given edge disconnects a graph
*/
public class Graph
{
	// Number of vertices in graph
	public int vertices;
	// Use to collect edges information
	public List < List < int >> adjacencylist;
	public Graph(int vertices)
	{
		this.vertices = vertices;
		this.adjacencylist = new List < List < int >> (vertices);
		for (int i = 0; i < this.vertices; ++i)
		{
			this.adjacencylist.Add(new List < int > ());
		}
	}
	public void addEdge(int u, int v)
	{
		if (u < 0 || u >= this.vertices || v < 0 || v >= this.vertices)
		{
			return;
		}
		// Add node edge
		this.adjacencylist[u].Add(v);
		this.adjacencylist[v].Add(u);
	}
	// Display graph nodes and edges
	public void printGraph()
	{
		Console.Write("\n Graph Adjacency List ");
		for (int i = 0; i < this.vertices; ++i)
		{
			Console.Write(" \n [" + i + "] :");
			// iterate edges of i node
			for (int j = 0; j < this.adjacencylist[i].Count; j++)
			{
				Console.Write("  " + this.adjacencylist[i][j]);
			}
		}
	}
	public void dfs(Boolean[] visited, int start)
	{
		if (start < 0 || start >= this.vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited[start] = true;
		int i = 0;
		// Execute edges of given start vertices
		while (i < this.adjacencylist[start].Count)
		{
			if (visited[this.adjacencylist[start][i]] == false)
			{
				// When edge node not visiting, then perform DFS operation
				this.dfs(visited, this.adjacencylist[start][i]);
			}
			// Visit to next node
			i++;
		}
	}
	public int edgePosition(int u, int v)
	{
		int i = 0;
		while (i < this.adjacencylist[u].Count)
		{
			if (this.adjacencylist[u][i] == v)
			{
				return i;
			}
			i++;
		}
		return -1;
	}
	public Boolean removeNodeEdge(int u, int v)
	{
		if (u < 0 || v < 0 || u > this.vertices || v > this.vertices)
		{
			return false;
		}
		int a = this.edgePosition(u, v);
		int b = this.edgePosition(v, u);
		if (a == -1 || b == -1)
		{
			// Given edge are not exist between given nodes 
			return false;
		}
		// Remove edges
		this.adjacencylist[u].RemoveAt(a);
		this.adjacencylist[v].RemoveAt(b);
		return true;
	}
	public void unsetVisit(Boolean[] visited)
	{
		for (int i = 0; i < this.vertices; ++i)
		{
			visited[i] = false;
		}
	}
	public Boolean isAllVerticesVisit(Boolean[] visited)
	{
		for (int i = 0; i < this.vertices; ++i)
		{
			if (visited[i] == false)
			{
				return false;
			}
		}
		return true;
	}
	public void disconnectByEdge(int u, int v)
	{
		Boolean[] visited = new Boolean[this.vertices];
		this.unsetVisit(visited);
		this.dfs(visited, 0);
		if (this.isAllVerticesVisit(visited) == true)
		{
			if (this.removeNodeEdge(u, v) == true)
			{
				this.unsetVisit(visited);
				this.dfs(visited, 0);
				// Add remove edge
				this.addEdge(u, v);
				if (this.isAllVerticesVisit(visited))
				{
					// not a bridge edge
					// graph are not disconnect
					Console.Write("\n Remove edge [" + u + "-" + 
                                  v + "] not disconnecting this graph ");
				}
				else
				{
					Console.Write("\n Remove edge [" + u + "-" + 
                                  v + "] disconnecting this graph ");
				}
			}
			else
			{
				// When edges are not exist
				Console.Write("\n No edge between vertices [" + u + 
                              "-" + v + "]");
			}
		}
		else
		{
			// When graph is already disconnected?
			Console.Write("\n Graph is already disconnected");
		}
	}
	public static void Main(String[] args)
	{
		Graph graph = new Graph(12);
		graph.addEdge(0, 1);
		graph.addEdge(0, 3);
		graph.addEdge(0, 4);
		graph.addEdge(1, 2);
		graph.addEdge(1, 5);
		graph.addEdge(2, 3);
		graph.addEdge(2, 6);
		graph.addEdge(3, 4);
		graph.addEdge(3, 9);
		graph.addEdge(6, 7);
		graph.addEdge(6, 8);
		graph.addEdge(9, 10);
		graph.addEdge(9, 11);
		graph.addEdge(10, 11);
		// Display graph element
		graph.printGraph();
		// Test case
		graph.disconnectByEdge(4, 7);
		graph.disconnectByEdge(3, 9);
		graph.disconnectByEdge(1, 2);
		graph.disconnectByEdge(6, 2);
		graph.disconnectByEdge(10, 11);
	}
}

input

 Graph Adjacency List
 [0] :  1  3  4
 [1] :  0  2  5
 [2] :  1  3  6
 [3] :  0  2  4  9
 [4] :  0  3
 [5] :  1
 [6] :  2  7  8
 [7] :  6
 [8] :  6
 [9] :  3  10  11
 [10] :  9  11
 [11] :  9  10
 No edge between vertices [4-7]
 Remove edge [3-9] disconnecting this graph
 Remove edge [1-2] not disconnecting this graph
 Remove edge [6-2] disconnecting this graph
 Remove edge [10-11] not disconnecting this graph
package main
import "fmt"
/*
    Go Program
    Check if removing a given edge disconnects a graph
*/
type Graph struct {
	// Number of vertices in graph
	vertices int
	// Use to collect edges information
	adjacencylist [][]int
}
func getGraph(vertices int) * Graph {
	var me *Graph = &Graph {}
	me.vertices = vertices
	me.adjacencylist = make([][]int,vertices)

	return me
}
func(this Graph) addEdge(u, v int) {
	if u < 0 || u >= this.vertices || v < 0 || v >= this.vertices {
		return
	}
	// Add node edge
	this.adjacencylist[u] = append(this.adjacencylist[u], v)
	this.adjacencylist[v] = append(this.adjacencylist[v], u)
}
// Display graph nodes and edges
func(this Graph) printGraph() {
	fmt.Print("\n Graph Adjacency List ")
	for i := 0 ; i < this.vertices ; i++ {
		fmt.Print(" \n [", i, "] :")
		// iterate edges of i node
		for j := 0 ; j < len(this.adjacencylist[i]) ; j++ {
			fmt.Print("  ", this.adjacencylist[i][j])
		}
	}
}
func(this Graph) dfs(visited[] bool, start int) {
	if start < 0 || start >= this.vertices {
		// In case given invalid node
		return
	}
	// Mark a current visited node
	visited[start] = true
	var i int = 0
	// Execute edges of given start vertices
	for (i < len(this.adjacencylist[start])) {
		if visited[this.adjacencylist[start][i]] == false {
			// When edge node not visiting, then perform DFS operation
			this.dfs(visited, this.adjacencylist[start][i])
		}
		// Visit to next node
		i++
	}
}
func(this Graph) edgePosition(u, v int) int {
	var i int = 0
	for (i < len(this.adjacencylist[u])) {
		if this.adjacencylist[u][i] == v {
			return i
		}
		i++
	}
	return -1
}
func(this Graph) removeNodeEdge(u, v int) bool {
	if u < 0 || v < 0 || u > this.vertices || v > this.vertices {
		return false
	}
	var a int = this.edgePosition(u, v)
	var b int = this.edgePosition(v, u)
	if a == -1 || b == -1 {
		// Given edge are not exist between given nodes 
		return false
	}
	// Remove edges
	this.adjacencylist[u] = append(this.adjacencylist[u][:a], 
		this.adjacencylist[u][(a+1):]...)
	this.adjacencylist[v] = append(this.adjacencylist[v][:b], 
		this.adjacencylist[v][(b+1):]...)

	return true
}
func(this Graph) unsetVisit(visited[] bool) {
	for i := 0 ; i < this.vertices ; i++ {
		visited[i] = false
	}
}
func(this Graph) isAllVerticesVisit(visited[] bool) bool {
	for i := 0 ; i < this.vertices ; i++ {
		if visited[i] == false {
			return false
		}
	}
	return true
}
func(this Graph) disconnectByEdge(u, v int) {
	var visited = make([]bool,this.vertices)
	this.unsetVisit(visited)
	this.dfs(visited, 0)
	if this.isAllVerticesVisit(visited) == true {
		if this.removeNodeEdge(u, v) == true {
			this.unsetVisit(visited)
			this.dfs(visited, 0)
			// Add remove edge
			this.addEdge(u, v)
			if this.isAllVerticesVisit(visited) {
				// not a bridge edge
				// graph are not disconnect
				fmt.Print("\n Remove edge [", u, "-", v, "] not disconnecting this graph ")
			} else {
				fmt.Print("\n Remove edge [", u, "-", v, "] disconnecting this graph ")
			}
		} else {
			// When edges are not exist
			fmt.Print("\n No edge between vertices [", u, "-", v, "]")
		}
	} else {
		// When graph is already disconnected?
		fmt.Print("\n Graph is already disconnected")
	}
}
func main() {
	var graph * Graph = getGraph(12)
	graph.addEdge(0, 1)
	graph.addEdge(0, 3)
	graph.addEdge(0, 4)
	graph.addEdge(1, 2)
	graph.addEdge(1, 5)
	graph.addEdge(2, 3)
	graph.addEdge(2, 6)
	graph.addEdge(3, 4)
	graph.addEdge(3, 9)
	graph.addEdge(6, 7)
	graph.addEdge(6, 8)
	graph.addEdge(9, 10)
	graph.addEdge(9, 11)
	graph.addEdge(10, 11)
	// Display graph element
	graph.printGraph()
	// Test case
	graph.disconnectByEdge(4, 7)
	graph.disconnectByEdge(3, 9)
	graph.disconnectByEdge(1, 2)
	graph.disconnectByEdge(6, 2)
	graph.disconnectByEdge(10, 11)
}

input

 Graph Adjacency List  
 [0] :  1  3  4 
 [1] :  0  2  5 
 [2] :  1  3  6 
 [3] :  0  2  4  9 
 [4] :  0  3 
 [5] :  1 
 [6] :  2  7  8 
 [7] :  6 
 [8] :  6 
 [9] :  3  10  11 
 [10] :  9  11 
 [11] :  9  10
 No edge between vertices [4-7]
 Remove edge [3-9] disconnecting this graph 
 Remove edge [1-2] not disconnecting this graph 
 Remove edge [6-2] disconnecting this graph 
 Remove edge [10-11] not disconnecting this graph
<?php
/*
    Php Program
    Check if removing a given edge disconnects a graph
*/
class Graph
{
	// Number of vertices in graph
	public $vertices;
	// Use to collect edges information
	public $adjacencylist;
	public	function __construct($vertices)
	{
		$this->vertices = $vertices;
		$this->adjacencylist = array();
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			$this->adjacencylist[] = array();
		}
	}
	public	function addEdge($u, $v)
	{
		if ($u < 0 || $u >= $this->vertices || 
            $v < 0 || $v >= $this->vertices)
		{
			return;
		}
		// Add node edge
		$this->adjacencylist[$u][] = $v;
		$this->adjacencylist[$v][] = $u;
	}
	// Display graph nodes and edges
	public	function printGraph()
	{
		echo("\n Graph Adjacency List ");
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			echo(" \n [".$i.
				"] :");
			// iterate edges of i node
			for ($j = 0; $j < count($this->adjacencylist[$i]); $j++)
			{
				echo("  ".$this->adjacencylist[$i][$j]);
			}
		}
	}
	public	function dfs(&$visited, $start)
	{
		if ($start < 0 || $start >= $this->vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		$visited[$start] = true;
		$i = 0;
		// Execute edges of given start vertices
		while ($i < count($this->adjacencylist[$start]))
		{
			if ($visited[$this->adjacencylist[$start][$i]] == false)
			{
				// When edge node not visiting, then perform DFS operation
				$this->dfs($visited, $this->adjacencylist[$start][$i]);
			}
			// Visit to next node
			$i++;
		}
	}
	public	function edgePosition($u, $v)
	{
		$i = 0;
		while ($i < count($this->adjacencylist[$u]))
		{
			if ($this->adjacencylist[$u][$i] == $v)
			{
				return $i;
			}
			$i++;
		}
		return -1;
	}
	public	function removeNodeEdge($u, $v)
	{
		if ($u < 0 || $v < 0 || 
            $u > $this->vertices || $v > $this->vertices)
		{
			return false;
		}
		$a = $this->edgePosition($u, $v);
		$b = $this->edgePosition($v, $u);
		if ($a == -1 || $b == -1)
		{
			// Given edge are not exist between given nodes 
			return false;
		}
		// Remove edges
		array_splice($this->adjacencylist[$u],$a,1);
		array_splice($this->adjacencylist[$v],$b,1);
		return true;
	}
	public	function unsetVisit(&$visited)
	{
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			$visited[$i] = false;
		}
	}
	public	function isAllVerticesVisit($visited)
	{
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			if ($visited[$i] == false)
			{
				return false;
			}
		}
		return true;
	}
	public	function disconnectByEdge($u, $v)
	{
		$visited = array_fill(0, $this->vertices, false);
		$this->unsetVisit($visited);
		$this->dfs($visited, 0);
		if ($this->isAllVerticesVisit($visited) == true)
		{
			if ($this->removeNodeEdge($u, $v) == true)
			{
				$this->unsetVisit($visited);
				$this->dfs($visited, 0);
				// Add remove edge
				$this->addEdge($u, $v);
				if ($this->isAllVerticesVisit($visited))
				{
					// not a bridge edge
					// graph are not disconnect
					echo("\n Remove edge [".$u.
						"-".$v.
						"] not disconnecting this graph ");
				}
				else
				{
					echo("\n Remove edge [".$u.
						"-".$v.
						"] disconnecting this graph ");
				}
			}
			else
			{
				// When edges are not exist
				echo("\n No edge between vertices [".$u.
					"-".$v.
					"]");
			}
		}
		else
		{
			// When graph is already disconnected?
			echo("\n Graph is already disconnected");
		}
	}
}

function main()
{
	$graph = new Graph(12);
	$graph->addEdge(0, 1);
	$graph->addEdge(0, 3);
	$graph->addEdge(0, 4);
	$graph->addEdge(1, 2);
	$graph->addEdge(1, 5);
	$graph->addEdge(2, 3);
	$graph->addEdge(2, 6);
	$graph->addEdge(3, 4);
	$graph->addEdge(3, 9);
	$graph->addEdge(6, 7);
	$graph->addEdge(6, 8);
	$graph->addEdge(9, 10);
	$graph->addEdge(9, 11);
	$graph->addEdge(10, 11);
	// Display graph element
	$graph->printGraph();
	// Test case
	$graph->disconnectByEdge(4, 7);
	$graph->disconnectByEdge(3, 9);
	$graph->disconnectByEdge(1, 2);
	$graph->disconnectByEdge(6, 2);
	$graph->disconnectByEdge(10, 11);
}
main();

input

 Graph Adjacency List
 [0] :  1  3  4
 [1] :  0  2  5
 [2] :  1  3  6
 [3] :  0  2  4  9
 [4] :  0  3
 [5] :  1
 [6] :  2  7  8
 [7] :  6
 [8] :  6
 [9] :  3  10  11
 [10] :  9  11
 [11] :  9  10
 No edge between vertices [4-7]
 Remove edge [3-9] disconnecting this graph
 Remove edge [1-2] not disconnecting this graph
 Remove edge [6-2] disconnecting this graph
 Remove edge [10-11] not disconnecting this graph
/*
    Node JS Program
    Check if removing a given edge disconnects a graph
*/
class Graph
{
	constructor(vertices)
	{
		this.vertices = vertices;
		this.adjacencylist = [];
		for (var i = 0; i < this.vertices; ++i)
		{
			this.adjacencylist.push([]);
		}
	}
	addEdge(u, v)
	{
		if (u < 0 || u >= this.vertices || 
            v < 0 || v >= this.vertices)
		{
			return;
		}
		// Add node edge
		this.adjacencylist[u].push(v);
		this.adjacencylist[v].push(u);
	}
	// Display graph nodes and edges
	printGraph()
	{
		process.stdout.write("\n Graph Adjacency List ");
		for (var i = 0; i < this.vertices; ++i)
		{
			process.stdout.write(" \n [" + i + "] :");
			// iterate edges of i node
			for (var j = 0; j < this.adjacencylist[i].length; j++)
			{
				process.stdout.write("  " + this.adjacencylist[i][j]);
			}
		}
	}
	dfs(visited, start)
	{
		if (start < 0 || start >= this.vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited[start] = true;
		var i = 0;
		// Execute edges of given start vertices
		while (i < this.adjacencylist[start].length)
		{
			if (visited[this.adjacencylist[start][i]] == false)
			{
				// When edge node not visiting, then perform DFS operation
				this.dfs(visited, this.adjacencylist[start][i]);
			}
			// Visit to next node
			i++;
		}
	}
	edgePosition(u, v)
	{
		var i = 0;
		while (i < this.adjacencylist[u].length)
		{
			if (this.adjacencylist[u][i] == v)
			{
				return i;
			}
			i++;
		}
		return -1;
	}
	removeNodeEdge(u, v)
	{
		if (u < 0 || v < 0 || 
            u > this.vertices || v > this.vertices)
		{
			return false;
		}
		var a = this.edgePosition(u, v);
		var b = this.edgePosition(v, u);
		if (a == -1 || b == -1)
		{
			// Given edge are not exist between given nodes 
			return false;
		}
		// Remove edges
		this.adjacencylist[u].splice(a, 1);
		this.adjacencylist[v].splice(b, 1);
		return true;
	}
	unsetVisit(visited)
	{
		for (var i = 0; i < this.vertices; ++i)
		{
			visited[i] = false;
		}
	}
	isAllVerticesVisit(visited)
	{
		for (var i = 0; i < this.vertices; ++i)
		{
			if (visited[i] == false)
			{
				return false;
			}
		}
		return true;
	}
	disconnectByEdge(u, v)
	{
		var visited = Array(this.vertices).fill(false);
		this.unsetVisit(visited);
		this.dfs(visited, 0);
		if (this.isAllVerticesVisit(visited) == true)
		{
			if (this.removeNodeEdge(u, v) == true)
			{
				this.unsetVisit(visited);
				this.dfs(visited, 0);
				// Add remove edge
				this.addEdge(u, v);
				if (this.isAllVerticesVisit(visited))
				{
					// not a bridge edge
					// graph are not disconnect
					process.stdout.write("\n Remove edge [" + 
                      u + "-" + v + "] not disconnecting this graph ");
				}
				else
				{
					process.stdout.write("\n Remove edge [" + 
                      u + "-" + v + "] disconnecting this graph ");
				}
			}
			else
			{
				// When edges are not exist
				process.stdout.write("\n No edge between vertices [" + 
                                    u + "-" + v + "]");
			}
		}
		else
		{
			// When graph is already disconnected?
			process.stdout.write("\n Graph is already disconnected");
		}
	}
}

function main()
{
	var graph = new Graph(12);
	graph.addEdge(0, 1);
	graph.addEdge(0, 3);
	graph.addEdge(0, 4);
	graph.addEdge(1, 2);
	graph.addEdge(1, 5);
	graph.addEdge(2, 3);
	graph.addEdge(2, 6);
	graph.addEdge(3, 4);
	graph.addEdge(3, 9);
	graph.addEdge(6, 7);
	graph.addEdge(6, 8);
	graph.addEdge(9, 10);
	graph.addEdge(9, 11);
	graph.addEdge(10, 11);
	// Display graph element
	graph.printGraph();
	// Test case
	graph.disconnectByEdge(4, 7);
	graph.disconnectByEdge(3, 9);
	graph.disconnectByEdge(1, 2);
	graph.disconnectByEdge(6, 2);
	graph.disconnectByEdge(10, 11);
}
main();

input

 Graph Adjacency List
 [0] :  1  3  4
 [1] :  0  2  5
 [2] :  1  3  6
 [3] :  0  2  4  9
 [4] :  0  3
 [5] :  1
 [6] :  2  7  8
 [7] :  6
 [8] :  6
 [9] :  3  10  11
 [10] :  9  11
 [11] :  9  10
 No edge between vertices [4-7]
 Remove edge [3-9] disconnecting this graph
 Remove edge [1-2] not disconnecting this graph
 Remove edge [6-2] disconnecting this graph
 Remove edge [10-11] not disconnecting this graph
#    Python 3 Program
#    Check if removing a given edge disconnects a graph
class Graph :
	#  Number of vertices in graph
	#  Use to collect edges information
	def __init__(self, vertices) :
		self.vertices = vertices
		self.adjacencylist = []
		i = 0
		while (i < self.vertices) :
			self.adjacencylist.append([])
			i += 1
		
	
	def addEdge(self, u, v) :
		if (u < 0 or u >= self.vertices or 
            v < 0 or v >= self.vertices) :
			return
		
		#  Add node edge
		self.adjacencylist[u].append(v)
		self.adjacencylist[v].append(u)
	
	#  Display graph nodes and edges
	def printGraph(self) :
		print("\n Graph Adjacency List ", end = "")
		i = 0
		while (i < self.vertices) :
			print(" \n [", i ,"] :", end = "")
			j = 0
			#  iterate edges of i node
			while (j < len(self.adjacencylist[i])) :
				print("  ", self.adjacencylist[i][j], end = "")
				j += 1
			
			i += 1
		
	
	def dfs(self, visited, start) :
		if (start < 0 or start >= self.vertices) :
			#  In case given invalid node
			return
		
		#  Mark a current visited node
		visited[start] = True
		i = 0
		#  Execute edges of given start vertices
		while (i < len(self.adjacencylist[start])) :
			if (visited[self.adjacencylist[start][i]] == False) :
				#  When edge node not visiting, then perform DFS operation
				self.dfs(visited, self.adjacencylist[start][i])
			
			#  Visit to next node
			i += 1
		
	
	def edgePosition(self, u, v) :
		i = 0
		while (i < len(self.adjacencylist[u])) :
			if (self.adjacencylist[u][i] == v) :
				return i
			
			i += 1
		
		return -1
	
	def removeNodeEdge(self, u, v) :
		if (u < 0 or v < 0 or u > self.vertices or v > self.vertices) :
			return False
		
		a = self.edgePosition(u, v)
		b = self.edgePosition(v, u)
		if (a == -1 or b == -1) :
			#  Given edge are not exist between given nodes 
			return False
		
		#  Remove edges
		del self.adjacencylist[u][a]
		del self.adjacencylist[v][b]
		return True
	
	def unsetVisit(self, visited) :
		i = 0
		while (i < self.vertices) :
			visited[i] = False
			i += 1
		
	
	def isAllVerticesVisit(self, visited) :
		i = 0
		while (i < self.vertices) :
			if (visited[i] == False) :
				return False
			
			i += 1
		
		return True
	
	def disconnectByEdge(self, u, v) :
		visited = [False] * (self.vertices)
		self.unsetVisit(visited)
		self.dfs(visited, 0)
		if (self.isAllVerticesVisit(visited) == True) :
			if (self.removeNodeEdge(u, v) == True) :
				self.unsetVisit(visited)
				self.dfs(visited, 0)
				#  Add remove edge
				self.addEdge(u, v)
				if (self.isAllVerticesVisit(visited)) :
					#  not a bridge edge
					#  graph are not disconnect
					print("\n Remove edge [", u ,
                          "-", v ,"] not disconnecting this graph ", end = "")
				else :
					print("\n Remove edge [", 
                          u ,"-", v ,"] disconnecting this graph ", end = "")
				
			else :
				#  When edges are not exist
				print("\n No edge between vertices [", 
                      u ,"-", v ,"]", end = "")
			
		else :
			#  When graph is already disconnected?
			print("\n Graph is already disconnected", end = "")
		
	

def main() :
	graph = Graph(12)
	graph.addEdge(0, 1)
	graph.addEdge(0, 3)
	graph.addEdge(0, 4)
	graph.addEdge(1, 2)
	graph.addEdge(1, 5)
	graph.addEdge(2, 3)
	graph.addEdge(2, 6)
	graph.addEdge(3, 4)
	graph.addEdge(3, 9)
	graph.addEdge(6, 7)
	graph.addEdge(6, 8)
	graph.addEdge(9, 10)
	graph.addEdge(9, 11)
	graph.addEdge(10, 11)
	#  Display graph element
	graph.printGraph()
	#  Test case
	graph.disconnectByEdge(4, 7)
	graph.disconnectByEdge(3, 9)
	graph.disconnectByEdge(1, 2)
	graph.disconnectByEdge(6, 2)
	graph.disconnectByEdge(10, 11)

if __name__ == "__main__": main()

input

 Graph Adjacency List
 [ 0 ] :   1   3   4
 [ 1 ] :   0   2   5
 [ 2 ] :   1   3   6
 [ 3 ] :   0   2   4   9
 [ 4 ] :   0   3
 [ 5 ] :   1
 [ 6 ] :   2   7   8
 [ 7 ] :   6
 [ 8 ] :   6
 [ 9 ] :   3   10   11
 [ 10 ] :   9   11
 [ 11 ] :   9   10
 No edge between vertices [ 4 - 7 ]
 Remove edge [ 3 - 9 ] disconnecting this graph
 Remove edge [ 1 - 2 ] not disconnecting this graph
 Remove edge [ 6 - 2 ] disconnecting this graph
 Remove edge [ 10 - 11 ] not disconnecting this graph
#    Ruby Program
#    Check if removing a given edge disconnects a graph
class Graph 
	# Define the accessor and reader of class Graph
	attr_reader :vertices, :adjacencylist
	attr_accessor :vertices, :adjacencylist
	#  Number of vertices in graph
	#  Use to collect edges information
	def initialize(vertices) 
		self.vertices = vertices
		self.adjacencylist = []
		i = 0
		while (i < self.vertices) 
			self.adjacencylist.push([])
			i += 1
		end

	end

	def addEdge(u, v) 
		if (u < 0 || u >= self.vertices || 
            v < 0 || v >= self.vertices) 
			return
		end

		#  Add node edge
		self.adjacencylist[u].push(v)
		self.adjacencylist[v].push(u)
	end

	#  Display graph nodes and edges
	def printGraph() 
		print("\n Graph Adjacency List ")
		i = 0
		while (i < self.vertices) 
			print(" \n [", i ,"] :")
			j = 0
			#  iterate edges of i node
			while (j < self.adjacencylist[i].length) 
				print("  ", self.adjacencylist[i][j])
				j += 1
			end

			i += 1
		end

	end

	def dfs(visited, start) 
		if (start < 0 || start >= self.vertices) 
			#  In case given invalid node
			return
		end

		#  Mark a current visited node
		visited[start] = true
		i = 0
		#  Execute edges of given start vertices
		while (i < self.adjacencylist[start].length) 
			if (visited[self.adjacencylist[start][i]] == false) 
				#  When edge node not visiting, then perform DFS operation
				self.dfs(visited, self.adjacencylist[start][i])
			end

			#  Visit to next node
			i += 1
		end

	end

	def edgePosition(u, v) 
		i = 0
		while (i < self.adjacencylist[u].length) 
			if (self.adjacencylist[u][i] == v) 
				return i
			end

			i += 1
		end

		return -1
	end

	def removeNodeEdge(u, v) 
		if (u < 0 || v < 0 || 
            u > self.vertices || v > self.vertices) 
			return false
		end

		a = self.edgePosition(u, v)
		b = self.edgePosition(v, u)
		if (a == -1 || b == -1) 
			#  Given edge are not exist between given nodes 
			return false
		end

		#  Remove edges
		self.adjacencylist[u].delete_at(a)
		self.adjacencylist[v].delete_at(b)
		return true
	end

	def unsetVisit(visited) 
		i = 0
		while (i < self.vertices) 
			visited[i] = false
			i += 1
		end

	end

	def isAllVerticesVisit(visited) 
		i = 0
		while (i < self.vertices) 
			if (visited[i] == false) 
				return false
			end

			i += 1
		end

		return true
	end

	def disconnectByEdge(u, v) 
		visited = Array.new(self.vertices) {false}
		self.unsetVisit(visited)
		self.dfs(visited, 0)
		if (self.isAllVerticesVisit(visited) == true) 
			if (self.removeNodeEdge(u, v) == true) 
				self.unsetVisit(visited)
				self.dfs(visited, 0)
				#  Add remove edge
				self.addEdge(u, v)
				if (self.isAllVerticesVisit(visited)) 
					#  not a bridge edge
					#  graph are not disconnect
					print("\n Remove edge [", 
                          u ,"-", v ,"] not disconnecting this graph ")
				else
 
					print("\n Remove edge [", 
                          u ,"-", v ,"] disconnecting this graph ")
				end

			else
 
				#  When edges are not exist
				print("\n No edge between vertices [", 
                      	u ,"-", v ,"]")
			end

		else
 
			#  When graph is already disconnected?
			print("\n Graph is already disconnected")
		end

	end

end

def main() 
	graph = Graph.new(12)
	graph.addEdge(0, 1)
	graph.addEdge(0, 3)
	graph.addEdge(0, 4)
	graph.addEdge(1, 2)
	graph.addEdge(1, 5)
	graph.addEdge(2, 3)
	graph.addEdge(2, 6)
	graph.addEdge(3, 4)
	graph.addEdge(3, 9)
	graph.addEdge(6, 7)
	graph.addEdge(6, 8)
	graph.addEdge(9, 10)
	graph.addEdge(9, 11)
	graph.addEdge(10, 11)
	#  Display graph element
	graph.printGraph()
	#  Test case
	graph.disconnectByEdge(4, 7)
	graph.disconnectByEdge(3, 9)
	graph.disconnectByEdge(1, 2)
	graph.disconnectByEdge(6, 2)
	graph.disconnectByEdge(10, 11)
end

main()

input

 Graph Adjacency List  
 [0] :  1  3  4 
 [1] :  0  2  5 
 [2] :  1  3  6 
 [3] :  0  2  4  9 
 [4] :  0  3 
 [5] :  1 
 [6] :  2  7  8 
 [7] :  6 
 [8] :  6 
 [9] :  3  10  11 
 [10] :  9  11 
 [11] :  9  10
 No edge between vertices [4-7]
 Remove edge [3-9] disconnecting this graph 
 Remove edge [1-2] not disconnecting this graph 
 Remove edge [6-2] disconnecting this graph 
 Remove edge [10-11] not disconnecting this graph 
import scala.collection.mutable._;
/*
    Scala Program
    Check if removing a given edge disconnects a graph
*/
class Graph(
	// Number of vertices in graph
	var vertices: Int,
		// Use to collect edges information
		var adjacencylist: ArrayBuffer[ArrayBuffer[Int]])
{
	def this(vertices: Int)
	{
		this(vertices,new ArrayBuffer[ArrayBuffer[Int]](vertices));
		var i: Int = 0;
		while (i < this.vertices)
		{
			this.adjacencylist += new ArrayBuffer[Int]();
			i += 1;
		}
	}
	def addEdge(u: Int, v: Int): Unit = {
		if (u < 0 || u >= this.vertices || 
             v < 0 || v >= this.vertices)
		{
			return;
		}
		// Add node edge
		adjacencylist(u) += v;
		adjacencylist(v) += u;
	}
	// Display graph nodes and edges
	def printGraph(): Unit = {
		print("\n Graph Adjacency List ");
		var i: Int = 0;
		while (i < this.vertices)
		{
			print(" \n [" + i + "] :");
			var j: Int = 0;
			// iterate edges of i node
			while (j < this.adjacencylist(i).size)
			{
				print("  " + this.adjacencylist(i)(j));
				j += 1;
			}
			i += 1;
		}
	}
	def dfs(visited: Array[Boolean], start: Int): Unit = {
		if (start < 0 || start >= this.vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited(start) = true;
		var i: Int = 0;
		// Execute edges of given start vertices
		while (i < adjacencylist(start).size)
		{
			if (visited(adjacencylist(start)(i)) == false)
			{
				// When edge node not visiting, then perform DFS operation
				dfs(visited, adjacencylist(start)(i));
			}
			// Visit to next node
			i += 1;
		}
	}
	def edgePosition(u: Int, v: Int): Int = {
		var i: Int = 0;
		while (i < this.adjacencylist(u).size)
		{
			if (this.adjacencylist(u)(i) == v)
			{
				return i;
			}
			i += 1;
		}
		return -1;
	}
	def removeNodeEdge(u: Int, v: Int): Boolean = {
		if (u < 0 || v < 0 || u > this.vertices || v > this.vertices)
		{
			return false;
		}
		var a: Int = edgePosition(u, v);
		var b: Int = edgePosition(v, u);
		if (a == -1 || b == -1)
		{
			// Given edge are not exist between given nodes 
			return false;
		}
		// Remove edges
		this.adjacencylist(u).remove(a);
		this.adjacencylist(v).remove(b);
		return true;
	}
	def unsetVisit(visited: Array[Boolean]): Unit = {
		var i: Int = 0;
		while (i < this.vertices)
		{
			visited(i) = false;
			i += 1;
		}
	}
	def isAllVerticesVisit(visited: Array[Boolean]): Boolean = {
		var i: Int = 0;
		while (i < this.vertices)
		{
			if (visited(i) == false)
			{
				return false;
			}
			i += 1;
		}
		return true;
	}
	def disconnectByEdge(u: Int, v: Int): Unit = {
		var visited: Array[Boolean] = 
          Array.fill[Boolean](this.vertices)(false);
		unsetVisit(visited);
		dfs(visited, 0);
		if (isAllVerticesVisit(visited) == true)
		{
			if (removeNodeEdge(u, v) == true)
			{
				unsetVisit(visited);
				dfs(visited, 0);
				// Add remove edge
				addEdge(u, v);
				if (isAllVerticesVisit(visited))
				{
					// not a bridge edge
					// graph are not disconnect
					print("\n Remove edge [" + u + 
                          "-" + v + "] not disconnecting this graph ");
				}
				else
				{
					print("\n Remove edge [" + u + 
                          "-" + v + "] disconnecting this graph ");
				}
			}
			else
			{
				// When edges are not exist
				print("\n No edge between vertices [" + 
                      		u + "-" + v + "]");
			}
		}
		else
		{
			// When graph is already disconnected?
			print("\n Graph is already disconnected");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var graph: Graph = new Graph(12);
		graph.addEdge(0, 1);
		graph.addEdge(0, 3);
		graph.addEdge(0, 4);
		graph.addEdge(1, 2);
		graph.addEdge(1, 5);
		graph.addEdge(2, 3);
		graph.addEdge(2, 6);
		graph.addEdge(3, 4);
		graph.addEdge(3, 9);
		graph.addEdge(6, 7);
		graph.addEdge(6, 8);
		graph.addEdge(9, 10);
		graph.addEdge(9, 11);
		graph.addEdge(10, 11);
		// Display graph element
		graph.printGraph();
		// Test case
		graph.disconnectByEdge(4, 7);
		graph.disconnectByEdge(3, 9);
		graph.disconnectByEdge(1, 2);
		graph.disconnectByEdge(6, 2);
		graph.disconnectByEdge(10, 11);
	}
}

input

 Graph Adjacency List
 [0] :  1  3  4
 [1] :  0  2  5
 [2] :  1  3  6
 [3] :  0  2  4  9
 [4] :  0  3
 [5] :  1
 [6] :  2  7  8
 [7] :  6
 [8] :  6
 [9] :  3  10  11
 [10] :  9  11
 [11] :  9  10
 No edge between vertices [4-7]
 Remove edge [3-9] disconnecting this graph
 Remove edge [1-2] not disconnecting this graph
 Remove edge [6-2] disconnecting this graph
 Remove edge [10-11] not disconnecting this graph
import Foundation;
/*
    Swift 4 Program
    Check if removing a given edge disconnects a graph
*/
class Graph
{
	// Number of vertices in graph
	var vertices: Int;
	// Use to collect edges information
	var adjacencylist: [[Int]];
	init(_ vertices: Int)
	{
		self.vertices = vertices;
		self.adjacencylist = [[Int]]();
		var i: Int = 0;
		while (i < self.vertices)
		{
			self.adjacencylist.append([Int]());
			i += 1;
		}
	}
	func addEdge(_ u: Int, _ v: Int)
	{
		if (u < 0 || u >= self.vertices || 
            v < 0 || v >= self.vertices)
		{
			return;
		}
		// Add node edge
		self.adjacencylist[u].append(v);
		self.adjacencylist[v].append(u);
	}
	// Display graph nodes and edges
	func printGraph()
	{
		print("\n Graph Adjacency List ", terminator: "");
		var i: Int = 0;
		while (i < self.vertices)
		{
			print(" \n [", i ,"] :", terminator: "");
			var j: Int = 0;
			// iterate edges of i node
			while (j < self.adjacencylist[i].count)
			{
				print("  ", self.adjacencylist[i][j], terminator: "");
				j += 1;
			}
			i += 1;
		}
	}
	func dfs(_ visited: inout[Bool], _ start: Int)
	{
		if (start < 0 || start >= self.vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited[start] = true;
		var i: Int = 0;
		// Execute edges of given start vertices
		while (i < self.adjacencylist[start].count)
		{
			if (visited[self.adjacencylist[start][i]] == false)
			{
				// When edge node not visiting, then perform DFS operation
				self.dfs(&visited, self.adjacencylist[start][i]);
			}
			// Visit to next node
			i += 1;
		}
	}
	func edgePosition(_ u: Int, _ v: Int) -> Int
	{
		var i: Int = 0;
		while (i < self.adjacencylist[u].count)
		{
			if (self.adjacencylist[u][i] == v)
			{
				return i;
			}
			i += 1;
		}
		return -1;
	}
	func removeNodeEdge(_ u: Int, _ v: Int) -> Bool
	{
		if (u < 0 || v < 0 || u > self.vertices || v > self.vertices)
		{
			return false;
		}
		let a: Int = self.edgePosition(u, v);
		let b: Int = self.edgePosition(v, u);
		if (a == -1 || b == -1)
		{
			// Given edge are not exist between given nodes 
			return false;
		}
		// Remove edges
		self.adjacencylist[u].remove(at: a);
		self.adjacencylist[v].remove(at: b);
		return true;
	}
	func unsetVisit(_ visited: inout[Bool])
	{
		var i: Int = 0;
		while (i < self.vertices)
		{
			visited[i] = false;
			i += 1;
		}
	}
	func isAllVerticesVisit(_ visited: [Bool]) -> Bool
	{
		var i: Int = 0;
		while (i < self.vertices)
		{
			if (visited[i] == false)
			{
				return false;
			}
			i += 1;
		}
		return true;
	}
	func disconnectByEdge(_ u: Int, _ v: Int)
	{
		var visited: [Bool] = Array(repeating: false, count: self.vertices);
		self.dfs(&visited, 0);
		if (self.isAllVerticesVisit(visited) == true)
		{
			if (self.removeNodeEdge(u, v) == true)
			{
				self.unsetVisit(&visited);
				self.dfs(&visited, 0);
				// Add remove edge
				self.addEdge(u, v);
				if (self.isAllVerticesVisit(visited))
				{
					// not a bridge edge
					// graph are not disconnect
					print("\n Remove edge [", u ,
                          "-", v ,"] not disconnecting this graph ", 
                          terminator: "");
				}
				else
				{
					print("\n Remove edge [", 
                          u ,"-", v ,"] disconnecting this graph ", 
                          terminator: "");
				}
			}
			else
			{
				// When edges are not exist
				print("\n No edge between vertices [", 
                      u ,"-", v ,"]", terminator: "");
			}
		}
		else
		{
			// When graph is already disconnected?
			print("\n Graph is already disconnected", terminator: "");
		}
	}
}
func main()
{
	let graph: Graph = Graph(12);
	graph.addEdge(0, 1);
	graph.addEdge(0, 3);
	graph.addEdge(0, 4);
	graph.addEdge(1, 2);
	graph.addEdge(1, 5);
	graph.addEdge(2, 3);
	graph.addEdge(2, 6);
	graph.addEdge(3, 4);
	graph.addEdge(3, 9);
	graph.addEdge(6, 7);
	graph.addEdge(6, 8);
	graph.addEdge(9, 10);
	graph.addEdge(9, 11);
	graph.addEdge(10, 11);
	// Display graph element
	graph.printGraph();
	// Test case
	graph.disconnectByEdge(4, 7);
	graph.disconnectByEdge(3, 9);
	graph.disconnectByEdge(1, 2);
	graph.disconnectByEdge(6, 2);
	graph.disconnectByEdge(10, 11);
}
main();

input

 Graph Adjacency List
 [ 0 ] :   1   3   4
 [ 1 ] :   0   2   5
 [ 2 ] :   1   3   6
 [ 3 ] :   0   2   4   9
 [ 4 ] :   0   3
 [ 5 ] :   1
 [ 6 ] :   2   7   8
 [ 7 ] :   6
 [ 8 ] :   6
 [ 9 ] :   3   10   11
 [ 10 ] :   9   11
 [ 11 ] :   9   10
 No edge between vertices [ 4 - 7 ]
 Remove edge [ 3 - 9 ] disconnecting this graph
 Remove edge [ 1 - 2 ] not disconnecting this graph
 Remove edge [ 6 - 2 ] disconnecting this graph
 Remove edge [ 10 - 11 ] not disconnecting this graph
/*
    Kotlin Program
    Check if removing a given edge disconnects a graph
*/
class Graph
{
	// Number of vertices in graph
	var vertices: Int;
	// Use to collect edges information
	var adjacencylist: MutableList < MutableList < Int >>;
	constructor(vertices: Int)
	{
		this.vertices = vertices;
		this.adjacencylist =  mutableListOf<MutableList<Int>>();
		var i: Int = 0;
		while (i < this.vertices)
		{
			this.adjacencylist.add(mutableListOf < Int > ());
			i += 1;
		}
	}
	fun addEdge(u: Int, v: Int): Unit
	{
		if (u < 0 || u >= this.vertices || 
            v < 0 || v >= this.vertices)
		{
			return;
		}
		// Add node edge
		this.adjacencylist[u].add(v);
		this.adjacencylist[v].add(u);
	}
	// Display graph nodes and edges
	fun printGraph(): Unit
	{
		print("\n Graph Adjacency List ");
		var i: Int = 0;
		while (i < this.vertices)
		{
			print(" \n [" + i + "] :");
			var j: Int = 0;
			// iterate edges of i node
			while (j < this.adjacencylist[i].size)
			{
				print("  " + this.adjacencylist[i][j]);
				j += 1;
			}
			i += 1;
		}
	}
	fun dfs(visited: Array < Boolean > , start: Int): Unit
	{
		if (start < 0 || start >= this.vertices)
		{
			// In case given invalid node
			return;
		}
		// Mark a current visited node
		visited[start] = true;
		var i: Int = 0;
		// Execute edges of given start vertices
		while (i < this.adjacencylist[start].size)
		{
			if (visited[this.adjacencylist[start][i]] == false)
			{
				// When edge node not visiting, then perform DFS operation
				this.dfs(visited, this.adjacencylist[start][i]);
			}
			// Visit to next node
			i += 1;
		}
	}
	fun edgePosition(u: Int, v: Int): Int
	{
		var i: Int = 0;
		while (i < this.adjacencylist[u].size)
		{
			if (this.adjacencylist[u][i] == v)
			{
				return i;
			}
			i += 1;
		}
		return -1;
	}
	fun removeNodeEdge(u: Int, v: Int): Boolean
	{
		if (u < 0 || v < 0 || 
            u > this.vertices || v > this.vertices)
		{
			return false;
		}
		val a: Int = this.edgePosition(u, v);
		val b: Int = this.edgePosition(v, u);
		if (a == -1 || b == -1)
		{
			// Given edge are not exist between given nodes 
			return false;
		}
		// Remove edges
		this.adjacencylist[u].removeAt(a);
		this.adjacencylist[v].removeAt(b);
		return true;
	}
	fun unsetVisit(visited: Array < Boolean > ): Unit
	{
		var i: Int = 0;
		while (i < this.vertices)
		{
			visited[i] = false;
			i += 1;
		}
	}
	fun isAllVerticesVisit(visited: Array < Boolean > ): Boolean
	{
		var i: Int = 0;
		while (i < this.vertices)
		{
			if (visited[i] == false)
			{
				return false;
			}
			i += 1;
		}
		return true;
	}
	fun disconnectByEdge(u: Int, v: Int): Unit
	{
		val visited: Array < Boolean > = Array(this.vertices)
		{
			false
		};
		this.unsetVisit(visited);
		this.dfs(visited, 0);
		if (this.isAllVerticesVisit(visited) == true)
		{
			if (this.removeNodeEdge(u, v) == true)
			{
				this.unsetVisit(visited);
				this.dfs(visited, 0);
				// Add remove edge
				this.addEdge(u, v);
				if (this.isAllVerticesVisit(visited))
				{
					// not a bridge edge
					// graph are not disconnect
					print("\n Remove edge [" + u + 
                          "-" + v + "] not disconnecting this graph ");
				}
				else
				{
					print("\n Remove edge [" + u 
                          + "-" + v + "] disconnecting this graph ");
				}
			}
			else
			{
				// When edges are not exist
				print("\n No edge between vertices [" + u + 
                      "-" + v + "]");
			}
		}
		else
		{
			// When graph is already disconnected?
			print("\n Graph is already disconnected");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val graph: Graph = Graph(12);
	graph.addEdge(0, 1);
	graph.addEdge(0, 3);
	graph.addEdge(0, 4);
	graph.addEdge(1, 2);
	graph.addEdge(1, 5);
	graph.addEdge(2, 3);
	graph.addEdge(2, 6);
	graph.addEdge(3, 4);
	graph.addEdge(3, 9);
	graph.addEdge(6, 7);
	graph.addEdge(6, 8);
	graph.addEdge(9, 10);
	graph.addEdge(9, 11);
	graph.addEdge(10, 11);
	// Display graph element
	graph.printGraph();
	// Test case
	graph.disconnectByEdge(4, 7);
	graph.disconnectByEdge(3, 9);
	graph.disconnectByEdge(1, 2);
	graph.disconnectByEdge(6, 2);
	graph.disconnectByEdge(10, 11);
}

input

 Graph Adjacency List
 [0] :  1  3  4
 [1] :  0  2  5
 [2] :  1  3  6
 [3] :  0  2  4  9
 [4] :  0  3
 [5] :  1
 [6] :  2  7  8
 [7] :  6
 [8] :  6
 [9] :  3  10  11
 [10] :  9  11
 [11] :  9  10
 No edge between vertices [4-7]
 Remove edge [3-9] disconnecting this graph
 Remove edge [1-2] not disconnecting this graph
 Remove edge [6-2] disconnecting this graph
 Remove edge [10-11] not disconnecting this graph

Resultant Output Explanation

It checks whether removing a given edge disconnects the graph and prints the results for the provided test cases.

Time Complexity

The time complexity of the algorithm depends on the number of vertices and edges in the graph. The DFS traversal has a time complexity of O(V + E), where 'V' is the number of vertices and 'E' is the number of edges. The edge removal and addition operations have constant time complexity.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post