1009: Back to Underworld

Problem Link

It is a bfs Problem

 

Try Enough?View Code

#include<bits/stdc++.h>
#define N 20005
using namespace std;
#define ll long long
vectorg[N];
int color[N];
#define pb push_back
#define bl 2
#define rd 1
#define nc 0

int bfs(int src)
{
queueq;
ll blck=0,red=0;
q.push(src);
color[src]=bl;
blck++;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<g[u].size();i++) { int v=g[u][i]; if(color[v]==0) { q.push(v); if(color[u]==bl) { color[v]=rd; red++; } else if(color[u]==rd) { color[v]=bl; blck++; } } } } return max(red,blck); } int main() { int t,cs=1,n=0; cin>>t;
while(t–)
{
cin>>n;
for(int i=0;i<N;i++) g[i].clear();
for(int i=0;i<n;i++) {int x,y; cin>>x>>y;
g[x].pb(y);
g[y].pb(x);
}

memset(color,0,sizeof color);
ll co=0;
for(int i=0;i<20005;i++)
{
if(!color[i] && !g[i].empty())
co+=bfs(i);
}
cout<<“Case “<<cs++<<“: “<<co<<endl;
}

}

 

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s