1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
3.1.
What is a Bipartite Graph?
3.2.
What is a weighted Graph?
3.3.
What is the difference between connected and non-connected components of a Graph?
4.
Conclusion
Last Updated: Mar 27, 2024
Hard

# Find the largest subset of Graph Vertices with Edges of 2 or more colors

Ayush Mishra
1 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

A graph is a type of non-linear data structure made up of vertices and edges. The vertices are also known as nodes, and edges are lines or arcs that connect any two nodes in the graph.

Formally, a graph is a pair of sets (v, e), where e is the set of edges connecting the pairs of vertices and v is the set of vertices.

This blog will discuss the problem of finding the largest subset of Graph Vertices with Edges of 2 or more colors. We will discuss this article in detail. Let's start going!

### Problem Statement

In this problem, we are given a complete undirected graph with N nodes or vertices in which the edges of the graph are colored. We are given a graph in the form of an adjacency matrix graph[][], where graph[i][j] is the color of the edge from vertex i to vertex j.

### Sample Examples

Example 1:

Input:

``````graph[][3]= {{0,2, 1},
{2, 0, 3},
{1, 3, 0}}                ``````

Output:

``3``

Explanation: All the nodes in the adjacency matrix have different color edges than one.

Example 2:

Input:

`````` graph[][3]= {{0,2, 1},
{2, 0, 3},
{1, 1, 0}} 			                ``````

Output:

`` 1``

Explanation: Only one node in the adjacency matrix has different color edges than one.

## Approach

We will traverse each and every node of the adjacent matrix and remove all the nodes having the same edge colors connected with different nodes. After removing all the nodes, return the count of the nodes having different color edges.

### Algorithm

âś”ď¸Ź Create an adjacent matrix graph[i][j].

âś”ď¸Ź Insert the vertices in a set.

âś”ď¸Ź If the size of the set is 1, return 1.

âś”ď¸Ź Traverse the Adjacent Matrix, and if the row and column index is not the same, insert them into a new set.

âś”ď¸Ź If the size of the new set is 1, remove the row index from the old set and return the size of the set.

### Implementation

C++ Program to find the largest subset of Graph Vertices with Edges of 2 or more colors.

``````#include <bits/stdc++.h>
using namespace std;

int largest_subset(int graph[][3])
{
set<int> v;
for (int i = 0; i < 3; i++)
{
v.insert(i);
}
while (!v.empty())
{
if (v.size() == 1)
{
return 1;
}
bool removed= false;
for (int x : v)
{
set<int> val;
for (int z : v)
{
if (z != x)
{
val.insert(graph[x][z]);
}
}
if (val.size() == 1)
{
v.erase(x);
removed = true;
break;
}
}
if (!removed)
{
break;
}
}

return v.size();
}

int main()
{
int graph[][3] = {{0,2,1}, {2,0,3}, {1,3,0}}

cout <<largest_subset(graph)<<endl;
return 0;
}``````

Output:

`` 3``

#### Time Complexity

The time complexity of the above approach for the problem of finding the largest subset of graph vertices with edges of 2 or more colors is O(n^3), as we have to visit every node of the graph matrix.

#### Space Complexity

The space complexity of the above approach for the problem of finding the largest subset of graph vertices with edges of 2 or more colors is O(n), as we are using extra space for storing the vertices in the set.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

### What is a Bipartite Graph?

A graph is a bipartite graph if and only if it can be colored in two ways. It is bipartite if and only if every edge belongs to an odd number of bonds, which are minimal subsets of edges whose removal increases the number of graph components.

### What is a weighted Graph?

Weighted graphs are graphs with weighted edges that represent the value of a variable. For Example, the weight of an edge in an airline route graph could represent the cost of travel from one city to another.

### What is the difference between connected and non-connected components of a Graph?

Every vertex in a connected graph has at least one path to every other vertex, whereas every vertex in a non-connected graph may or may not be connected to every other vertex.

## Conclusion

Congratulations on finishing the blog! We have studied the problem of finding the largest subset of graph vertices with edges of 2 or more colors.

We hope this blog has helped you enhance your knowledge regarding the topic of Graph data structure, and if you want to learn more, then you can check articles on:-

Please refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Please do upvote our blogs if you find them helpful and informative!

Happy learning!

Live masterclass