Check if every vertex triplet in graph contains two vertices connected to third vertex
Given an undirected graph with N vertices and K edges, the task is to check if for every combination of three vertices in the graph, there exists two vertices which are connected to third vertex. In other words, for every vertex triplet (a, b, c), if there exists a path between a and c, then there should also exist a path between b and c.
Examples:
Input: N = 4, K = 3
Edges: 1 -> 2, 2 -> 3, 3 -> 4
Output: YES
Explanation:
Since the whole graph is connected, the above condition will always be valid.Input: N = 5 and K = 3
Edges: 1 -> 3, 3 -> 4, 2 -> 5.
Output: NO
Explanation:
If we consider the triplet (1, 2, 3) then there is a path between vertices 1 and 3 but there is no path between vertices 2 and 3.
Approach: Follow the steps below to solve the problem –
- Traverse the graph by DFS Traversal technique from any component and maintain two variables to store the component minimum and component maximum.
- Store every component maximum and minimum in a vector.
- Now, if any two components have an intersection in their minimum and maximum values interval, then there will exist a valid (a < b < c) triplet. Hence, both of the components should be connected. Otherwise, the graph is not valid.
Below is the implementation of the above approach
C++
// C++ program of the// above approach#include <bits/stdc++.h>using namespace std;// Function to add edge into// the graphvoid addEdge(vector<int> adj[], int u, int v){ adj[u].push_back(v); adj[v].push_back(u);}void DFSUtil(int u, vector<int> adj[], vector<bool>& visited, int& componentMin, int& componentMax){ visited[u] = true; // Finding the maximum and // minimum values in each component componentMax = max(componentMax, u); componentMin = min(componentMin, u); for (int i = 0; i < adj[u].size(); i++) if (visited[adj[u][i]] == false) DFSUtil(adj[u][i], adj, visited, componentMin, componentMax);}// Function for checking whether// the given graph is valid or notbool isValid(vector<pair<int, int> >& v){ int MAX = -1; bool ans = 0; // Checking for intersecting intervals for (auto i : v) { // If intersection is found if (i.first <= MAX) { // Graph is not valid ans = 1; } MAX = max(MAX, i.second); } return (ans == 0 ? 1 : 0);}// Function for the DFS Traversalvoid DFS(vector<int> adj[], int V){ std::vector<pair<int, int> > v; // Traversing for every vertex vector<bool> visited(V, false); for (int u = 1; u <= V; u++) { if (visited[u] == false) { int componentMax = u; int componentMin = u; DFSUtil(u, adj, visited, componentMin, componentMax); // Storing maximum and minimum // values of each component v.push_back({ componentMin, componentMax }); } } bool check = isValid(v); if (check) cout << "Yes"; else cout << "No"; return;}// Driver codeint main(){ int N = 4, K = 3; vector<int> adj[N + 1]; addEdge(adj, 1, 2); addEdge(adj, 2, 3); addEdge(adj, 3, 4); DFS(adj, N); return 0;} |
Java
// Java program of the // above approachimport java.util.*;import java.lang.*;class GFG{ static class pair{ int first, second; pair(int first, int second) { this.first = first; this.second = second; }}// Function to add edge into// the graphstatic void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v){ adj.get(u).add(v); adj.get(v).add(u);}static void DFSUtil(int u, ArrayList<ArrayList<Integer>> adj, boolean[] visited, int componentMin, int componentMax){ visited[u] = true; // Finding the maximum and // minimum values in each component componentMax = Math.max(componentMax, u); componentMin = Math.min(componentMin, u); for(int i = 0; i < adj.get(u).size(); i++) if (visited[adj.get(u).get(i)] == false) DFSUtil(adj.get(u).get(i), adj, visited, componentMin, componentMax);}// Function for checking whether// the given graph is valid or notstatic boolean isValid(ArrayList<pair> v){ int MAX = -1; boolean ans = false; // Checking for intersecting intervals for(pair i : v) { // If intersection is found if (i.first <= MAX) { // Graph is not valid ans = true; } MAX = Math.max(MAX, i.second); } return (ans == false ? true : false);}// Function for the DFS Traversalstatic void DFS(ArrayList<ArrayList<Integer>> adj, int V){ ArrayList<pair> v = new ArrayList<>(); // Traversing for every vertex boolean[] visited = new boolean[V + 1]; for(int u = 1; u <= V; u++) { if (visited[u] == false) { int componentMax = u; int componentMin = u; DFSUtil(u, adj, visited, componentMin, componentMax); // Storing maximum and minimum // values of each component v.add(new pair(componentMin, componentMax)); } } boolean check = isValid(v); if (check) System.out.println("Yes"); else System.out.println("No"); return;}// Driver codepublic static void main (String[] args){ int N = 4, K = 3; ArrayList<ArrayList<Integer>> adj = new ArrayList<>(); for(int i = 0; i <= N + 1; i++) adj.add(new ArrayList<>()); addEdge(adj, 1, 2); addEdge(adj, 2, 3); addEdge(adj, 3, 4); DFS(adj, N);}}// This code is contributed by offbeat |
Python3
# Python3 program of the# above approach# Function to add edge into# the graphdef addEdge(adj, u, v): adj[u].append(v) adj[v].append(u) return adjdef DFSUtil(u, adj, visited, componentMin, componentMax): visited[u] = True # Finding the maximum and # minimum values in each component componentMax = max(componentMax, u) componentMin = min(componentMin, u) for i in range(len(adj[u])): if (visited[adj[u][i]] == False): visited, componentMax, componentMin = DFSUtil( adj[u][i], adj, visited, componentMin, componentMax) return visited, componentMax, componentMin# Function for checking whether# the given graph is valid or notdef isValid(v): MAX = -1 ans = False # Checking for intersecting intervals for i in v: if len(i) != 2: continue # If intersection is found if (i[0] <= MAX): # Graph is not valid ans = True MAX = max(MAX, i[1]) return (True if ans == False else False)# Function for the DFS Traversaldef DFS(adj, V): v = [[]] # Traversing for every vertex visited = [False for i in range(V + 1)] for u in range(1, V + 1): if (visited[u] == False): componentMax = u componentMin = u visited, componentMax, componentMin = DFSUtil( u, adj, visited, componentMin, componentMax) # Storing maximum and minimum # values of each component v.append([componentMin, componentMax]) check = isValid(v) if (check): print('Yes') else: print('No') return# Driver codeif __name__=="__main__": N = 4 K = 3 adj = [[] for i in range(N + 1)] adj = addEdge(adj, 1, 2) adj = addEdge(adj, 2, 3) adj = addEdge(adj, 3, 4) DFS(adj, N)# This code is contributed by rutvik_56 |
C#
// C# program of the // above approachusing System;using System.Collections;using System.Collections.Generic; class GFG{ class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; }} // Function to add edge into// the graphstatic void addEdge(ArrayList adj, int u, int v){ ((ArrayList)adj[u]).Add(v); ((ArrayList)adj[v]).Add(u);} static void DFSUtil(int u, ArrayList adj, bool[] visited, int componentMin, int componentMax){ visited[u] = true; // Finding the maximum and // minimum values in each component componentMax = Math.Max(componentMax, u); componentMin = Math.Min(componentMin, u); for(int i = 0; i < ((ArrayList)adj[u]).Count; i++) if (visited[(int)((ArrayList)adj[u])[i]] == false) DFSUtil((int)((ArrayList)adj[u])[i], adj, visited, componentMin, componentMax);} // Function for checking whether// the given graph is valid or notstatic bool isValid(ArrayList v){ int MAX = -1; bool ans = false; // Checking for intersecting intervals foreach(pair i in v) { // If intersection is found if (i.first <= MAX) { // Graph is not valid ans = true; } MAX = Math.Max(MAX, i.second); } return (ans == false ? true : false);} // Function for the DFS Traversalstatic void DFS(ArrayList adj, int V){ ArrayList v = new ArrayList(); // Traversing for every vertex bool[] visited = new bool[V + 1]; for(int u = 1; u <= V; u++) { if (visited[u] == false) { int componentMax = u; int componentMin = u; DFSUtil(u, adj, visited, componentMin, componentMax); // Storing maximum and minimum // values of each component v.Add(new pair(componentMin, componentMax)); } } bool check = isValid(v); if (check) Console.WriteLine("Yes"); else Console.WriteLine("No"); return;} // Driver codepublic static void Main(string[] args){ int N = 4; ArrayList adj = new ArrayList(); for(int i = 0; i <= N + 1; i++) adj.Add(new ArrayList()); addEdge(adj, 1, 2); addEdge(adj, 2, 3); addEdge(adj, 3, 4); DFS(adj, N);}}// This code is contributed by pratham76 |
Javascript
<script>// JavaScript program of the // above approach class pair{ constructor(first, second) { this.first = first; this.second = second; }} // Function to add edge into// the graphfunction addEdge(adj,u, v){ (adj[u]).push(v); (adj[v]).push(u);} function DFSUtil(u, adj, visited, componentMin, componentMax){ visited[u] = true; // Finding the maximum and // minimum values in each component componentMax = Math.max(componentMax, u); componentMin = Math.min(componentMin, u); for(var i = 0; i < (adj[u]).length; i++) if (visited[(adj[u])[i]] == false) DFSUtil((adj[u])[i], adj, visited, componentMin, componentMax);} // Function for checking whether// the given graph is valid or notfunction isValid(v){ var MAX = -1; var ans = false; // Checking for intersecting intervals for(var i of v) { // If intersection is found if (i.first <= MAX) { // Graph is not valid ans = true; } MAX = Math.max(MAX, i.second); } return (ans == false ? true : false);} // Function for the DFS Traversalfunction DFS(adj, V){ var v = []; // Traversing for every vertex var visited = Array(V+1).fill(false); for(var u = 1; u <= V; u++) { if (visited[u] == false) { var componentMax = u; var componentMin = u; DFSUtil(u, adj, visited, componentMin, componentMax); // Storing maximum and minimum // values of each component v.push(new pair(componentMin, componentMax)); } } var check = isValid(v); if (check) document.write("Yes"); else document.write("No"); return;} // Driver codevar N = 4; var adj = []; for(var i = 0; i <= N + 1; i++) adj.push(new Array()); addEdge(adj, 1, 2);addEdge(adj, 2, 3);addEdge(adj, 3, 4); DFS(adj, N);</script> |
Output:
Yes
Time Complexity: O(N + E)
Auxiliary Space: O(N)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
