Latest Updates ☛
- Graphs: Introduction of graphs and types of graphs
- SPOJ : Geeky solves geeky solution
- Solution Code : Pass the time problem on SPOJ.
- Find the minimum shortest path solution in c language ! !
- Code
Author
Welcome !
Heya ! Firstly thanks for giving look to this website .Here you can find all the stuff related to programming plus its solutions means a pack for learners and coders.
So keep visiting and enjoy learning and browsing this Code Author ! !
About Me
- Java Programs
- C++
C++ Programs List
- Books
- C & Data Structures
Data Structures
Reference Book
This is a basic book for a starter to learn data structures in c programming language.Filled with total explanation of all programs working and many more.Read more...
- Privacy Policy
- Others
Friday, September 6, 2013
SPOJ : Problem Joey the President filmwala's solution
Question :
Joey is the new president of USA. Not really, just in a movie. As a president he was asked to divide a group of islands into some cities. He thought that if any two islands are connected by a bridge, they should be the part of the same city. For ex: If there are six islands, they will be numbered as 1, 2, 3, 4, 5 and 6 and suppose that island 1 is connected to island 2 and island 3 by wo bridges, also island 5 is connected to island 6, then he should divide the islands into 3 cities with islands sets as {1,2,3}, {4} and {5,6}. Given the number of islands and information about the bridges, can you tell him what is the maximum number of cities into which he can divide the islands?
Joey is the new president of USA. Not really, just in a movie. As a president he was asked to divide a group of islands into some cities. He thought that if any two islands are connected by a bridge, they should be the part of the same city. For ex: If there are six islands, they will be numbered as 1, 2, 3, 4, 5 and 6 and suppose that island 1 is connected to island 2 and island 3 by wo bridges, also island 5 is connected to island 6, then he should divide the islands into 3 cities with islands sets as {1,2,3}, {4} and {5,6}. Given the number of islands and information about the bridges, can you tell him what is the maximum number of cities into which he can divide the islands?
Inputs
First line will contain two integers "N" the number of islands and "B" the number of bridges. Each of the next "B" lines will contain two integers "A" and "B" which means that island numbered as "A" is connected to island numbered as "B".
Outputs :
Print a single integer denoting the maximum number of cities into which Joey can divide the islands.
Print a single integer denoting the maximum number of cities into which Joey can divide the islands.
Constraints
1 <= N <= 10^5, 0 <= B <= Min(10^5,N*(N-1)/2)
1 <= N <= 10^5, 0 <= B <= Min(10^5,N*(N-1)/2)
Level : Thinker,Admirer
Solution to the Problem :
#include<stdio.h>
int par[100005];
void unionss(int *par,int src,int dest,int n)
{
int t;
t=src;
if(par[dest]==-1)
par[dest]=src;
else
{
int k=par[dest];
if(k>src)
{
unionss(par,src,k,n);
}
else
{
par[dest]=src;
unionss(par,k,src,n);
}
}
}
int find(int *par,int l)
{
int t=l;
while(par[t]!=-1)
t=par[t];
return(t);
}
main()
{
int n,b;
scanf("%d%d",&n,&b);
int i;
for(i=0;i<n;i++)
par[i]=-1;
int j;
for(j=0;j<b;j++)
{
int src,dest;
scanf("%d%d",&src,&dest);
int j=find(par,src-1);
int k=find(par,dest-1);
if(src>dest)
{
int t=src;
src=dest;
dest=t;
}
if(j==k)
{
if(j==-1&&k==-1)
unionss(par,src-1,dest-1,n);
}
else
unionss(par,src-1,dest-1,n);
}
int c=0;
for(i=0;i<n;i++)
{
if(par[i]==-1)
c++;
}
printf("%d\n",c);
}
No comments :
Post a Comment