Samsung Interview Question
Software EngineersCountry: India
#include<iostream>
using namespace std;
int n;
int g[100][100]={0};// adjacency matrix
bool Bipartite(int i,int color[])
{
bool yes=true;
for(int j=1;j<=n;j++)
{
if(g[i][j])// if the edge exist from i to j node
{
if(color[j]==-1)
{
color[j]=1-color[i];
yes=yes & Bipartite(j,color);
}
else if(color[j]==color[i])//if the color of adjacent node is same then its not Bipartite
return false;
}
}
return yes;
}
int main()
{
int e; //e is no of edges of the graph
cin>>n>>e; // n is the number of nodes
int color[n];
for(int i=1;i<=n;i++)
color[i]=-1; // -1 means that the node is not colored
for(int i=1;i<=e;i++)
{
int a,b;
cin>>a>>b;
g[a][b]=1; // specify the edges
g[b][a]=1;
}
for(int i=1;i<=n;i++)
{
if(color[i]==-1)
{
color[i]=0; // initialize the color of source node as 0
if(!Bipartite(i,color))
{
cout<<-1<<endl;
return 0;
}
}
}
for(int i=1;i<=n;i++)
{
if(color[i]=0)
cout<<i<<" ";//prints the edges with same color lets say 0 denotes red color and 1 denotes blue color
}
return 0;
}
#include<iostream>
using namespace std;
int n;
int g[100][100]={0};// adjacency matrix
bool Bipartite(int i,int color[])
{
bool yes=true;
for(int j=1;j<=n;j++)
{
if(g[i][j])// if the edge exist from i to j node
{
if(color[j]==-1)
{
color[j]=1-color[i];
yes=yes & Bipartite(j,color);
}
else if(color[j]==color[i])//if the color of adjacent node is same then its not Bipartite
return false;
}
}
return yes;
}
int main()
{
int e; //e is no of edges of the graph
cin>>n>>e; // n is the number of nodes
int color[n];
for(int i=1;i<=n;i++)
color[i]=-1; // -1 means that the node is not colored
for(int i=1;i<=e;i++)
{
int a,b;
cin>>a>>b;
g[a][b]=1; // specify the edges
g[b][a]=1;
}
for(int i=1;i<=n;i++)
{
if(color[i]==-1)
{
color[i]=0; // initialize the color of source node as 0
if(!Bipartite(i,color))
{
cout<<-1<<endl;
return 0;
}
}
}
for(int i=1;i<=n;i++)
{
if(color[i]=0)
cout<<i<<" ";//prints the edges with same color lets say 0 denotes red color and 1 denotes blue color
}
return 0;
}
#include<iostream>
using namespace std;
int n;
int g[100][100]={0};// adjacency matrix
bool Bipartite(int i,int color[])
{
bool yes=true;
for(int j=1;j<=n;j++)
{
if(g[i][j])// if the edge exist from i to j node
{
if(color[j]==-1)
{
color[j]=1-color[i];
yes=yes & Bipartite(j,color);
}
else if(color[j]==color[i])//if the color of adjacent node is same then its not Bipartite
return false;
}
}
return yes;
}
int main()
{
int e; //e is no of edges of the graph
cin>>n>>e; // n is the number of nodes
int color[n];
for(int i=1;i<=n;i++)
color[i]=-1; // -1 means that the node is not colored
for(int i=1;i<=e;i++)
{
int a,b;
cin>>a>>b;
g[a][b]=1; // specify the edges
g[b][a]=1;
}
for(int i=1;i<=n;i++)
{
if(color[i]==-1)
{
color[i]=0; // initialize the color of source node as 0
if(!Bipartite(i,color))
{
cout<<-1<<endl;
return 0;
}
}
}
for(int i=1;i<=n;i++)
{
if(color[i]=0)
cout<<i<<" ";//prints the edges with same color lets say 0 denotes red color and 1 denotes blue color
}
return 0;
}
#include<iostream>
using namespace std;
int n;
int g[100][100]={0};// adjacency matrix
bool Bipartite(int i,int color[])
{
bool yes=true;
for(int j=1;j<=n;j++)
{
if(g[i][j])// if the edge exist from i to j node
{
if(color[j]==-1)
{
color[j]=1-color[i];
yes=yes & Bipartite(j,color);
}
else if(color[j]==color[i])//if the color of adjacent node is same then its not Bipartite
return false;
}
}
return yes;
}
int main()
{
int e; //e is no of edges of the graph
cin>>n>>e; // n is the number of nodes
int color[n];
for(int i=1;i<=n;i++)
color[i]=-1; // -1 means that the node is not colored
for(int i=1;i<=e;i++)
{
int a,b;
cin>>a>>b;
g[a][b]=1; // specify the edges
g[b][a]=1;
}
for(int i=1;i<=n;i++)
{
if(color[i]==-1)
{
color[i]=0; // initialize the color of source node as 0
if(!Bipartite(i,color))
{
cout<<-1<<endl;
return 0;
}
}
}
for(int i=1;i<=n;i++)
{
if(color[i]==0)
cout<<i<<" ";//prints the edges with same color lets say 0 denotes red color and 1 denotes blue color
}
return 0;
}
Ueieheiiwhsi
- Anonymous November 23, 2018