10583 - Ubiquitous Religions

[rotoZOOM]

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]

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]

Ya, look up "Union-Find".

[Eduard]

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;
read(n,m);
if (m=0) and (n=0) then goto 1;
for i:=1 to m do
read(u,v);
kap(k);
writeln('Case ',number,': ',k);
until (m=0) and (n=0);
1:
end.
[/pascal]

[lord_burgos]

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]

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

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]

Was it Spanish? Or Espaniol

[horape]

Was it Spanish? Or Espaniol

Yes. Espa

[Dmytro Chernysh]

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]

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]

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]

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]

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]

My algo is:
read pair(x,y)
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]

There may also be a pair where i == j, so a pair of the same student.