Given an undirected graph G with vertices numbered in the range [1, N] and an array Edges[][] consisting of M edges, the task is to check if all triplets of the undirected graph satisfies the transitive property or not. If found to be true, then print “YES”. Otherwise, print “NO”.
Transitive property of an undirected graph states that:
If vertex X is connected to vertex Y, vertex Y is connected to vertex Z, then vertex X must be connected to the vertex Z.
Examples:
Input: N = 4, M = 3 Edges[] = {{1, 3}, {3, 4}, {1, 4}}
Output: YES
Explanation:
Input : N = 4, M = 4, Edges[] = {{3, 1}, {2, 3}, {3, 4}, {1, 2}}
Output: NO
Explanation:
Naive Approach: The simplest approach to solve the above problem is to traverse over every triplet of vertices (i, j, k), and for each such triplet, check if there is an edge between vertices j and k if i and j, and i and k are directly connected by an edge with the help of an adjacency matrix.
Time Complexity: O(N3)
Auxiliary Space: O(N2)
Efficient Approach: The idea is to find all the connected components present in the graph. Finally, check if all the connected components of the graph are a complete graph or not. If found to be true, then print “YES”. Otherwise, print “NO”. Follow the steps below to solve the problem:
- Represent the graph, G in the form of adjacency list.
- Find all the connected components of the graph and check if the connected component is a complete graph or not by performing the following operations:
- Find total count of vertices in the current connected graph say, X.
- If all the vertices of the connected component are not connected to X – 1 vertices, then print “NO”.
- Finally, check if all the connected components are a complete graph or not. IF found to be true, then print “YES”.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Stores undirected graph using// adjacency list representationclass Graph { // Stores count of vertices int V; // adj[i]: Store all the nodes // connected to i list<int>* adj; // DFS function void DFSUtil(int v, bool visited[], int id[], int id_number, int& c);public: Graph(int V); ~Graph(); // Connect two vertices v and w void addEdge(int v, int w); // Check if the connected component // is a complete graph or not bool connectedComponents();};Graph::Graph(int V){ this->V = V; adj = new list<int>[V + 1];}// DestructorGraph::~Graph() { delete[] adj; }// Function to add an undirected// edge between two verticesvoid Graph::addEdge(int v, int w){ adj[v].push_back(w); adj[w].push_back(v);}// Function to find all the connected// components of a graph using DFSvoid Graph::DFSUtil(int v, bool visited[], int id[], int id_number, int& c){ // Mark the vertex v as visited visited[v] = true; // Assign an id of current // connected component id[v] = id_number; // Increase the count of vertices in // current connected component c++; // Recursively call for all the // vertices adjacent to this vertex list<int>::iterator i; // Iterate over all the adjacent // vertices of the current vertex for (i = adj[v].begin(); i != adj[v].end(); ++i) { // If current vertex is not visited if (!visited[*i]) DFSUtil(*i, visited, id, id_number, c); }}// Function to find connected// components of the graphbool Graph::connectedComponents(){ bool* visited = new bool[V + 1]; // id[i]: Stores an unique id of connected // component in which vertex i exists int* id = new int[V + 1]; // Store count of nodes in current // connected component int* component_size = new int[V + 1]; // Mark all the vertices as not visited for (int v = 1; v <= V; v++) visited[v] = false; for (int v = 1; v <= V; v++) { // If vertex v is not marked if (visited[v] == false) { // Stores the size of a component // in which vertex v lies int c = 0; // Stores id of current // connected component int id_number = v; DFSUtil(v, visited, id, id_number, c); // Stores count of vertices of // current component component_size[v] = c; } else { component_size[v] = component_size[id[v]]; } } // Iterate over all the vertices for (int v = 1; v <= V; v++) { // IF connected component[v] is // not a complete graph if (component_size[v] - 1 != (int)adj[v].size()) { delete[] visited; return false; } } delete[] visited; return true;}// Function to check if graph is// Edge Transitive or notvoid isTransitive(int N, int M, vector<vector<int> > Edge){ // Initialize a graph Graph G(N); // Traverse the array Edge[] for (int i = 0; i < M; i++) { G.addEdge(Edge[i][0], Edge[i][1]); } // If all the connected components // are a complete graph int f = G.connectedComponents(); if (f == 0) { cout << "NO\n"; } else { cout << "YES\n"; }}// Driver Codeint main(){ // Input int N = 4, M = 3; vector<vector<int> > Edge{ { 1, 3 }, { 3, 4 }, { 1, 4 } }; isTransitive(N, M, Edge); return 0;} |
Java
// Java program of the above approachimport java.util.*;class Graph { // Stores count of vertices int V; // adj[i]: Store all the nodes // connected to i ArrayList<Integer>[] adj; // DFS function void DFSUtil(int v, boolean[] visited, int[] id, int id_number, int[] component_size) { // Mark the vertex v as visited visited[v] = true; // Assign an id of current // connected component id[v] = id_number; // Increase the count of vertices in // current connected component component_size[id_number]++; // Recursively call for all the // vertices adjacent to this vertex for (Integer i : adj[v]) { // If current vertex is not visited if (!visited[i]) DFSUtil(i, visited, id, id_number, component_size); } } // Function to find connected // components of the graph boolean connectedComponents() { boolean[] visited = new boolean[V + 1]; int[] id = new int[V + 1]; int[] component_size = new int[V + 1]; // Mark all the vertices as not visited for (int v = 1; v <= V; v++) visited[v] = false; for (int v = 1; v <= V; v++) { // If vertex v is not marked if (!visited[v]) { int id_number = v; DFSUtil(v, visited, id, id_number, component_size); } } // Iterate over all the vertices for (int v = 1; v <= V; v++) { // IF connected component[v] is // not a complete graph if (component_size[id[v]] - 1 != adj[v].size()) { return false; } } return true; } // Function to initialize graph Graph(int V) { this.V = V; adj = (ArrayList<Integer>[]) new ArrayList[V + 1]; for (int i = 0; i <= V; i++) { adj[i] = new ArrayList<>(); } } // Function to connect two vertices v and w void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); }}class Main { // Function to check if graph is // Edge Transitive or not static void isTransitive(int N, int M, int[][] Edge) { // Initialize a graph Graph G = new Graph(N); // Traverse the array Edge[] for (int i = 0; i < M; i++) { G.addEdge(Edge[i][0], Edge[i][1]); } // If all the connected components // are a complete graph if (G.connectedComponents()) { System.out.println("YES"); } else { System.out.println("NO"); } } // Driver code public static void main(String[] args) { int N = 4, M = 3; int[][] Edge = { { 1, 3 }, { 3, 4 }, { 1, 4 } }; isTransitive(N, M, Edge); }} |
Python3
# Python3 program of the above approach# Function to add an undirected# edge between two verticesdef addEdge(v, w): global adj adj[v].append(w) adj[w].append(v)# Function to find all the connected# components of a graph using DFSdef DFSUtil(v, id, id_number): global visited, adj, c # Mark the vertex v as visited visited[v] = True # Assign an id of current # connected component id[v] = id_number # Increase the count of vertices in # current connected component c += 1 # Iterate over all the adjacent # vertices of the current vertex for i in adj[v]: # If current vertex is not visited if (not visited[i]): DFSUtil(i, id, id_number)# Function to find connected# components of the graphdef connectedComponents(): global V, adj, visited, c # id[i]: Stores an unique id of connected # component in which vertex i exists id = [0]*(V + 1) # Store count of nodes in current # connected component component_size = [0]*(V + 1) for v in range(1, V + 1): # If vertex v is not marked if (visited[v] == False): # Stores the size of a component # in which vertex v lies c = 0 # Stores id of current # connected component id_number = v DFSUtil(v, id, id_number) # Stores count of vertices of # current component component_size[v] = c else: component_size[v] = component_size[id[v]] # Iterate over all the vertices for v in range(1, V + 1): # IF connected component[v] is # not a complete graph if (component_size[v] - 1 != len(adj[v])): return False return True# Function to check if graph is# Edge Transitive or notdef isTransitive(N, M, Edge): global adj, visited, c # Traverse the array Edge[] for i in range(M): addEdge(Edge[i][0], Edge[i][1]) # If all the connected components # are a complete graph f = connectedComponents() if (f == 0): print("NO") else: print("YES")# Driver Codeif __name__ == '__main__': # Input V, c = 5, 0 adj = [[] for i in range(V + 1)] visited = [False] * (V + 1) N, M = 4, 3 Edge = [ [ 1, 3 ], [ 3, 4 ], [ 1, 4 ] ] isTransitive(N, M, Edge) # This code is contributed by mohit kumar 29 |
C#
using System;using System.Collections.Generic;public class Graph { // Stores count of vertices public int V; // adj[i]: Store all the nodes // connected to i public List<int>[] adj; // DFS function public void DFSUtil(int v, bool[] visited, int[] id, int id_number, int[] component_size) { // Mark the vertex v as visited visited[v] = true; // Assign an id of current // connected component id[v] = id_number; // Increase the count of vertices in // current connected component component_size[id_number]++; // Recursively call for all the // vertices adjacent to this vertex foreach(int i in adj[v]) { // If current vertex is not visited if (!visited[i]) { DFSUtil(i, visited, id, id_number, component_size); } } } // Function to find connected // components of the graph public bool connectedComponents() { bool[] visited = new bool[V + 1]; int[] id = new int[V + 1]; int[] component_size = new int[V + 1]; // Mark all the vertices as not visited for (int v = 1; v <= V; v++) { visited[v] = false; } for (int v = 1; v <= V; v++) { // If vertex v is not marked if (!visited[v]) { int id_number = v; DFSUtil(v, visited, id, id_number, component_size); } } // Iterate over all the vertices for (int v = 1; v <= V; v++) { // IF connected component[v] is // not a complete graph if (component_size[id[v]] - 1 != adj[v].Count) { return false; } } return true; } // Function to initialize graph public Graph(int V) { this.V = V; adj = new List<int>[ V + 1 ]; for (int i = 0; i <= V; i++) { adj[i] = new List<int>(); } } // Function to connect two vertices v and w public void addEdge(int v, int w) { adj[v].Add(w); adj[w].Add(v); }}public class Program { // Function to check if graph is // Edge Transitive or not static void isTransitive(int N, int M, int[][] Edge) { // Initialize a graph Graph G = new Graph(N); // Traverse the array Edge[] for (int i = 0; i < M; i++) { G.addEdge(Edge[i][0], Edge[i][1]); } // If all the connected components // are a complete graph if (G.connectedComponents()) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } } // Driver code public static void Main(string[] args) { int N = 4, M = 3; int[][] Edge = new int[3][]; Edge[0] = new int[] { 1, 3 }; Edge[1] = new int[] { 3, 4 }; Edge[2] = new int[] { 1, 4 }; isTransitive(N, M, Edge); }} |
Javascript
// JavaScript program of the above approachclass Graph { // Stores count of vertices constructor(V) { this.V = V; this.adj = new Array(V + 1).fill().map(() => []); } // DFS function DFSUtil(v, visited, id, id_number, component_size) { // Mark the vertex v as visited visited[v] = true; // Assign an id of current // connected component id[v] = id_number; // Increase the count of vertices in // current connected component component_size[id_number]++; // Recursively call for all the // vertices adjacent to this vertex for (let i of this.adj[v]) { // If current vertex is not visited if (!visited[i]) this.DFSUtil(i, visited, id, id_number, component_size); } } // Function to find connected // components of the graph connectedComponents() { const visited = new Array(this.V + 1).fill(false); const id = new Array(this.V + 1).fill(0); const component_size = new Array(this.V + 1).fill(0); // Mark all the vertices as not visited for (let v = 1; v <= this.V; v++) visited[v] = false; for (let v = 1; v <= this.V; v++) { // If vertex v is not marked if (!visited[v]) { const id_number = v; this.DFSUtil(v, visited, id, id_number, component_size); } } // Iterate over all the vertices for (let v = 1; v <= this.V; v++) { // IF connected component[v] is // not a complete graph if (component_size[id[v]] - 1 !== this.adj[v].length) { return false; } } return true; } // Function to connect two vertices v and w addEdge(v, w) { this.adj[v].push(w); this.adj[w].push(v); }}// Function to check if graph is// Edge Transitive or notfunction isTransitive(N, M, Edge) { // Initialize a graph const G = new Graph(N); // Traverse the array Edge[] for (let i = 0; i < M; i++) { G.addEdge(Edge[i][0], Edge[i][1]); } // If all the connected components // are a complete graph if (G.connectedComponents()) { console.log("YES"); } else { console.log("NO"); }}const N = 4, M = 3;const Edge = [[1, 3], [3, 4], [1, 4]];isTransitive(N, M, Edge);// This code is contributed by sankar. |
Output:
YES
Time Complexity: O(N + M)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
