## 10583 - Ubiquitous Religions

Moderator: Board moderators

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

### 10583 - Ubiquitous Religions

Hi !

This problem very simple. It was easiest on online contest.
But I don't understand how to solve it.
In order to merge two groups of the same religions we have to O(N^2) algo. But N can be 50000, so I can't use this algorithm.

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
Hello!

You needn't O(N^2) operations to merge two groups. O(N) is enough, I suppose.
And moreover when you merge two groups you have to attach the smaller one to the bigger one.

All this results in O(NlogN) algorithm.

Have AC.
Andrey.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Ya, look up "Union-Find".

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### 10583

Ithing this is a problem which whant to find how many components does the graph have.Am i wrong???
if not then tell me why this program gets WA.
[pascal]label 1;
var a,u,v:array[1..50000] of longint;
i,j,k,n,m,number:longint;
procedure kap(var k:longint);
var i,j,p:longint;
f:boolean;
s:array[1..50000] of longint;
begin
k:=0;
for i:=1 to 50000 do
s:=0;
for p:=1 to n do
if s[p]=0 then
begin
k:=k+1;
s[p]:=k;
repeat
f:=true;
for i:=1 to n do
if s=k then
for j:=1 to m do
if (u[j]=i) and (s[v[j]]<>k) then begin s[v[j]]:=k;f:=false; end else
if (v[j]=i) and (s[u[j]]<>k) then begin s[u[j]]:=k;f:=false; end;
until f=true;
end;
end;
begin
number:=0;
repeat
for i:=1 to 50000 do
begin u:=0;v:=0;end;
number:=number+1;
if (m=0) and (n=0) then goto 1;
for i:=1 to m do
kap(k);
writeln('Case ',number,': ',k);
until (m=0) and (n=0);
1:
end.
[/pascal]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

### 10583

No entiendo por que es WA, creo que el problemas se resuelve de este modo.

1) si los dos numero que te dan no pertenecen a una religion se marcan como una nueva religion
2) Si uno no tiene religion y el otro si , entoces , al que no tiene religion pertenece a la religion del otro
y 3) si los dos tiene religion y no son de la misma, entoces eliminamos una por que no hay razon para contarla, ya que estas dos son la misma

Mi codigo:
[cpp]
# include <stdio.h>
# define N 50000

long a[N+1];
char b[N+1];

main(){
long n, m, i, j, k, x, y,min , max,set=0;
while(scanf("%ld %ld",&n,&m) != EOF && (n || m)){
printf("Case %ld:",++set);
for(i=0;i<=N;i++) b = a = 0;
k = 1;
for(i=0;i<m;i++){
scanf("%ld %ld",&x,&y);
if(!a[x] && !a[y]) a[x] = a[y] = ++k;
else
if((!a[x] && a[y])||(!a[y] && a[x])) a[x] = a[y] =(a[x] > a[y])?a[x]:a[y];
else
if(a[x] != a[y]){
max =(a[x] > a[y])?a[x]:a[y];
b[max] = 1;
}
}
k = 0;
for(i=1;i<=n;i++)
if(a && !b[a]){ k++; b[a]=1;}
else if(!a) k++;

printf(" %ld\n",k);
}
return 0;
}

[/cpp]

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

### Re: 10583

El idioma de este foro es ingles, por favor trata de usarlo.

lord_burgos wrote:No entiendo por que es WA, creo que el problemas se resuelve de este modo:

...
Prueba con:

Code: Select all

``````20 20
12 4
6 11
17 7
10 7
7 17
10 16
14 16
19 15                                                                                                         10 13
9 17                                                                                                          18 2
10 12                                                                                                         8 18
9 19
9 15                                                                                                          17 8
5 15                                                                                                          12 17
19 11
4 3
0 0
``````
El resultado correcto es 3, tu programa da 4.

Saludos,
HoraPe

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
Was it Spanish? Or Espaniol

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires
Dmytro Chernysh wrote:Was it Spanish? Or Espaniol
Yes. Espa

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
However, we all should post here English and only English!
Moreover, you are a member of Algorithmic Team... so you should give good examples

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires
Dmytro Chernysh wrote:However, we all should post here English and only English!
Moreover, you are a member of Algorithmic Team... so you should give good examples
Yes, english is to be preferred, and that's what my reply said, but it is corteous to answer in the same language that the question was done.

If you like, i'll edit my post and add a translation.

Saludos,
HoraPe

rlatif119
New poster
Posts: 16
Joined: Mon Mar 01, 2004 4:00 pm
Location: Dhaka

### 10583....WA.....sample input needed

I think my algorithm to solve this problem is very simple and correct (i hope). but it generates WA. can someone please help me finding the problem or giving me more sample input so i can check.
Here is my code

[c]

#include<stdio.h>

void religion_count(long n,long m);

long tot;
main()
{
long i,j,n,m;
while(1)
{
scanf("%ld%ld",&n,&m);
if(n==0 && m==0)
break;
religion_count(n,m);
}

}

void religion_count(long n,long m)
{
long rel[50000],i,j,s1,s2,count;

for(i=0;i<n;++i)
rel=0;
count=0;

for(i=0;i<m;++i)
{
scanf("%ld%ld",&s1,&s2);
if(rel[s1-1]!=0)
rel[s2-1]=rel[s1-1];
else if(rel[s2-1]!=0)
rel[s1-1]=rel[s2-1];
else if(rel[s1-1]==0 && rel[s2-1]==0)
rel[s1-1]=++count; rel[s2-1]=count;
}
if(n==0)
printf("Case %ld: 0\n",++tot);
else if(m==0)
printf("Case %ld: %ld\n",++tot,n);
else
{
for(i=0;i<n;++i)
if(rel==0)
++count;

printf("Case %ld: %ld\n",++tot,count);
}
}[/c]

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
Hi,

Try this input:
4 3
1 2
3 4
1 3
0 0
Output should be 1, but I think your program will output 2.

Anggakusuma

Silverfox03
New poster
Posts: 6
Joined: Fri Aug 27, 2004 4:05 pm

### 10583 WA, help!

My Code:
[cpp]
#include <iostream.h>
#include <fstream.h>

#ifdef ONLINE_JUDGE
istream &fin=cin;
#else
ifstream fin("10583.in");
#endif

void Judge(long int rel[2],long int group[50001],long int rels[50001][2],long int *p,long int *g,long int *r)
{
if (group[rel[0]]==0&&group[rel[1]]==0)
{
(*p)+=2;
(*g)++;
group[rel[0]]=group[rel[1]]=*g;
}
else if (group[rel[0]]!=0&&group[rel[1]]==0)
{
(*p)++;
group[rel[1]]=group[rel[0]];
}
else if (group[rel[0]]==0&&group[rel[1]]!=0)
{
(*p)++;
group[rel[0]]=group[rel[1]];
}
else if (group[rel[0]]!=group[rel[1]])
{
rels[*r][0]=group[rel[0]];
rels[*r][1]=group[rel[1]];
(*r)++;
}
}

void Print(long int c,long int num)
{
cout<<"Case "<<c<<": "<<num<<endl;
}

main()
{
long int group[50001],rel[50001][2],n,m,p,g,r,num,i,c,t[2];

fin>>n>>m;
c=0;
while (!(n==0&&m==0))
{
c++;
p=g=r=0;
num=n;
for (i=0;i<n+1;i++)
group=0;
for (i=0;i<m;i++)
{
fin>>t[0]>>t[1];
Judge(t,group,rel,&p,&g,&r);
}
num=num-p+g;
while (r!=0)
{
for (i=0;i<g+1;i++)
group=0;
m=r;
p=g=r=0;
for (i=0;i<m;i++)
Judge(rel,group,rel,&p,&g,&r);
num=num-p+g;
}
Print(c,num);
fin>>n>>m;
}

return 0;
}
[/cpp]

I know my algo maybe strange, but I think it's right.
Can someone help me, or give me some input?
Thanks!

Silverfox03
New poster
Posts: 6
Joined: Fri Aug 27, 2004 4:05 pm

### My algo

My algo is:
1.if neither of x and y is labeled
person+2;(person is the number of person that I have visited)
group++;(group is the number of groups)
label x and y with group;
2.if one of them is labeled and another isn't
person++;
make them label the same
3.if both of them are labeled but have different group number
record their group number for a new pair

After I check all the original pairs, there are a lot of pairs left that created by step 3. I regard a group as a person, and do above again. By this, I finish the union of different group.
What's wrong with it?

N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:
There may also be a pair where i == j, so a pair of the same student.