Last active
May 8, 2020 12:07
-
-
Save gunpreet34/c47f05ff80c75bfd13453f73f4727bcb to your computer and use it in GitHub Desktop.
Samsung coding round question: Given a graph print either of the set of the vertices that are colored with the same color. And if the graph is not bipartite print “-1”. Test cases also included the cases when a graph is not connected.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
using namespace std; | |
int n; | |
int arr[100][100]={0}; | |
bool isBiPartite(int i,int color[]){ | |
bool flag = true; | |
for(int j=0;j<n;j++){ | |
if(arr[i][j] == 1){ | |
if(color[j] == -1){//If color of current node not set | |
color[j] = 1 - color[i];//Set color opposite to adjacent node | |
flag = flag & isBiPartite(j,color);//Check for adjacent node | |
}else if(color[i] == color[j]){//If color is same for adjacent node return false | |
return false; | |
} | |
} | |
} | |
return flag; | |
} | |
int main(){ | |
cin >> n;//No of nodes in graph | |
int color[n];//For coloring of graph | |
for(int i=0;i<n;i++){ | |
color[i] = -1; | |
for(int j=0;j<n;j++){ | |
cin >> arr[i][j];//Input graph adjacency matrix | |
} | |
} | |
for(int i=0;i<n;i++){ | |
if(color[i]==-1){ | |
color[i] = 0;//Color starting node(of connected/disconnected graph) as 0 | |
if(!isBiPartite(i,color)){//If not bipartite then print -1 | |
cout << "-1" << endl; | |
return 0; | |
} | |
} | |
} | |
for(int i=0;i<n;i++){ | |
if(color[i] == 0){ | |
cout << i << " ";//Print all nodes with color 0 | |
} | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
please, give a test case as input that's why we can easily understand your code