459:Graph Connectivity

#Reference In BANGLA

www.shafaetsplanet.com

In ENGLISH

Topcoder

Hackerearth

Implementation

Stackoverflow<3

 

Problem Link

Solution

#include<bits/stdc++.h>
using namespace std;
int parent[28],pos[28];
void makeSet(int n)
{
parent[n]=n;
pos[n]=0;

}
int find(int n)
{
return parent[n]==n?n:find(parent[n]);

}
int Union(int a,int b)

{
int u=find(a);
int v=find(b);

if(pos[u]>pos[v])
{
parent[v]=u;
}

else{
parent[u]=v;
if(pos[u]==pos[v])
pos[v]++;
}
}
int main()
{
int tc;
int ans;
scanf(“%d\n”,&tc);
while(tc–){
string st;
getline(cin,st);

int n=st[0]-‘A’+1;

ans=n;
for(int i=0;i<n;i++)
makeSet(i);

while(1)
{
if(!getline(cin,st)||st.empty())
{
break;}
int x=find(st[0]-‘A’),y=find(st[1]-‘A’);
if(x!=y){
Union(x,y);
ans–;
}
}
cout<<ans<<endl;
if(tc)
cout<<endl;
}
return 0;
}

 

 

 

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized and tagged , , . 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