➤ Problem Link : 1093D. Beautiful Graph
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll m = 998244353;
vector<int> adj[300001];
bool visited[300001];
bool visited2[300001];
int color[300001];
int color2[300001];
ll dfs(int v,int n,int p,int oe)
{
ll ans=1;
color[v]=oe;
if(oe==1)
{
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
if(!visited[adj[v][i]])
{
visited[adj[v][i]]=1;
ans=(ans*dfs(adj[v][i],n,v,2))%m;
}
else
{
if(color[adj[v][i]]==1)
{
return 0;
}
}
}
// cout<<ans<<endl;
ans=(ans*2)%m;
return ans;
}
else
{
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
if(!visited[adj[v][i]])
{
visited[adj[v][i]]=1;
ans=(ans*dfs(adj[v][i],n,v,1))%m;
}
else
{
if(color[adj[v][i]]==2)
{
return 0;
}
}
}
// cout<<ans<<endl;
return ans%m;
}
}
ll dfs2(int v,int n,int p,int oe)
{
ll ans=1;
color2[v]=oe;
if(oe==1)
{
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
if(!visited2[adj[v][i]])
{
visited2[adj[v][i]]=1;
ans=(ans*dfs2(adj[v][i],n,v,2))%m;
}
else
{
if(color2[adj[v][i]]==1)
{
return 0;
}
}
}
// cout<<ans<<endl;
ans=(ans*2)%m;
return ans;
}
else
{
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
if(!visited2[adj[v][i]])
{
visited2[adj[v][i]]=1;
ans=(ans*dfs2(adj[v][i],n,v,1))%m;
}
else
{
if(color2[adj[v][i]]==2)
{
return 0;
}
}
}
// cout<<ans<<endl;
return ans%m;
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,e,u,v;
cin>>n>>e;
bool flag=0;
for(int i=0;i<=n;i++)
{
adj[i].clear();
visited[i]=0;
visited2[i]=0;
color[i]=0;
color2[i]=0;
}
for(int i=0;i<e;i++)
{
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
ll cnt=1;
for(int i=1;i<=n;i++)
{
ll tmp=-1,tmp2=-1;
if(!visited[i])
{
visited[i]=1;
tmp=dfs(i,n,-1,1)%m;
if(!tmp)
{
flag=1;
break;
}
}
if(!visited2[i])
{
visited2[i]=1;
tmp2=dfs2(i,n,-1,2)%m;
if(!tmp2)
{
flag=1;
break;
}
tmp=(tmp2 + tmp)%m;
}
if(tmp>0)
cnt=(cnt*tmp)%m;
}
if(flag)
cout<<"0\n";
else
cout<<cnt<<"\n";
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.