Using Colouring


#1

int col[100001];
vectoradj[100001];
int vis[100001];
bool dfs(int node,int bit)
{
vis[node]=1;
col[node]=bit;
for(int child:adj[node])
{
if(vis[child]==0)
{
if(dfs(child,bit^1)==false) return false;
}
else
{
if(col[node]==col[child]) return false;
}
}
return true;
}
int Solution::solve(int A, vector<vector > &B) {
for(int i=1;i<=A;i++)
{
vis[i]=0;
adj[i].clear();
col[i]=-1;
}
for(int i=0;i<B.size();i++)
{
adj[B[i][0]].push_back(B[i][1]);
adj[B[i][1]].push_back(B[i][0]);
}
for(int i=1;i<=A;i++)
{
if(vis[i]==0)
{
if(dfs(i,0)==false) return false;
}
}
return true;
}