11503 - Virtual Friends

tapan_chugh · Post by **tapan_chugh** » Fri Dec 28, 2012 10:03 pm

Guys i am using the union-find algo and map.
However I am getting TLE. Can anybody help ?
Below is my code

AC..

brianfry713 · Post by **brianfry713** » Sat Dec 29, 2012 11:31 pm

Try making your maps global.

tapan_chugh · Post by **tapan_chugh** » Sun Dec 30, 2012 11:15 am

thanks brianfry713

enyazoroism · Post by **enyazoroism** » Sun Mar 31, 2013 7:26 pm

I tried all test data above and got correct answers but kept receiving WA.
I use find with compression algorithm from wiki http://en.wikipedia.org/wiki/Disjoint-s ... _structure
Can anyone help me

THX

Code: Select all

AC

brianfry713 · Post by **brianfry713** » Tue Apr 02, 2013 12:57 am

input:

Code: Select all

10
30
w n
r l
b b
q m
h b
d c
r a
o z
k w
y k
i h
d d
s q
d c
r x
m j
w o
r f
s x
y j
l b
b d
f e
a s
c r
y b
e n
d c
g y
x g
30
p x
l k
r o
l e
n l
p m
p a
f q
k w
o h
k p
c m
q o
n h
n w
u k
w e
s h
m q
b g
u b
c q
j l
i j
s v
m w
k d
t q
x b
x i
30
v m
r t
b r
j l
t p
s n
f n
z w
f q
m j
f a
d a
r r
s w
f o
b s
n c
v u
h q
f f
s b
q a
w x
q p
a c
e c
c h
z h
f v
k r
30
l m
o n
j z
p k
p q
r x
x j
i k
z t
x y
c a
h b
k h
c i
c q
e o
d n
o t
f m
d g
d w
f w
g c
x p
q i
k v
y u
d t
c l
d g
30
w e
t h
c a
o i
o h
d r
q t
v k
c w
g s
p s
o q
m q
b s
a o
u g
n w
y n
x q
z n
g l
g d
p w
t b
w r
l b
s n
d a
u e
u g
30
m u
q o
d c
u r
e b
o t
y k
h x
a o
h c
d w
m v
x x
d r
y r
l x
n m
q d
u t
w k
g a
l m
j e
u u
w k
i c
x b
b u
m u
n e
30
e m
a y
d t
m r
d y
a i
x j
o l
h g
q i
m f
h z
v l
h i
o j
v u
u s
o y
p y
y a
l u
e y
m i
o u
e t
z h
i r
c i
s f
p k
30
g g
b k
i b
z p
r z
u z
x c
m a
u l
f d
k y
r g
o u
z w
i g
o o
b o
p p
e l
l q
p w
a h
j p
a n
q d
d h
n c
w v
t d
j x
30
m b
p y
p p
a h
x u
s n
u p
g s
h d
i i
q x
b m
j f
j x
v c
d u
s j
y u
b i
e y
m b
s w
q i
o y
g y
x y
m y
e z
y v
z p
30
j v
g e
b e
o e
f c
f u
s t
d x
x i
i t
s g
e i
h e
c k
z h
f d
i l
r l
q j
n f
z x
q t
s r
b v
p s
y k
s h
n e
p b
k p

AC output:

Code: Select all

enyazoroism · Post by **enyazoroism** » Wed Apr 03, 2013 10:43 am

brianfry713

Got ACed, THX a lot!!!!
my compression wasn't done in setunion.

jdalbey · Post by **jdalbey** » Tue Nov 26, 2013 7:41 am

Here's a tip: The specification says "A name is a string of 1 to 20 letters (uppercase or lowercase). " But what it doesn't say is that the input is CASE-SENSITIVE. An upper case name and a lower case version of the same name are TWO DIFFERENT NAMES. For example:

Code: Select all

1
3
a b
A B
a A

produces

Code: Select all

2
2
4

NOT

Code: Select all

2
2
2

uDebug · Post by **uDebug** » Thu Feb 06, 2014 2:19 pm

brianfry713,

Thanks very much for the amazing test cases you've shared with us. Those, along with your help / guidance really helped me out a bunch on this problem.

Also, for anyone else new to union-find algorithms and union find set data structures (as I was when I started this problem), I found Professor Sedgewick's slides incredibly helpful to get me thinking in the right direction

http://www.cs.princeton.edu/~rs/AlgsDS0 ... onFind.pdf

piyukr · Post by **piyukr** » Wed Feb 19, 2014 12:07 pm

brianfry713, my code gives the same output as expected on the sample test that you gave. I checked it using the 'diff' command in linux. But on submission I got WA, can you please help me know what is wrong? I have commented my code .It is here : http://ideone.com/uMYQpa

uDebug · Post by **uDebug** » Wed Feb 19, 2014 12:24 pm

piyukr wrote:But on submission I got WA, can you please help me know what is wrong?

Looks like you're forgetting to print a newline after the last output.

Try the following input:

Code: Select all

1
12
A F
G H
R T
H R
H H
W P
Z A
T T
E T
Q X
X U
U T

AC Output:

Code: Select all

Note that your code does not print a newline after the "8".

piyukr · Post by **piyukr** » Wed Feb 19, 2014 1:02 pm

I have added the new line , still it says WA. here's the modified code: http://ideone.com/evOPNK

brianfry713 · Post by **brianfry713** » Wed Feb 19, 2014 9:34 pm

Input:

Code: Select all

10
100
w n
r l
b b
q m
h b
d c
r a
o z
k w
y k
i h
d d
s q
d c
r x
m j
w o
r f
s x
y j
l b
b d
f e
a s
c r
y b
e n
d c
g y
x g
p x
l k
r o
l e
n l
p m
p a
f q
k w
o h
k p
c m
q o
n h
n w
u k
w e
s h
m q
b g
u b
c q
j l
i j
s v
m w
k d
t q
x b
x i
v m
r t
b r
j l
t p
s n
f n
z w
f q
m j
f a
d a
r r
s w
f o
b s
n c
v u
h q
f f
s b
q a
w x
q p
a c
e c
c h
z h
f v
k r
l m
o n
j z
p k
p q
r x
x j
i k
z t
x y
100
c a
h b
k h
c i
c q
e o
d n
o t
f m
d g
d w
f w
g c
x p
q i
k v
y u
d t
c l
d g
w e
t h
c a
o i
o h
d r
q t
v k
c w
g s
p s
o q
m q
b s
a o
u g
n w
y n
x q
z n
g l
g d
p w
t b
w r
l b
s n
d a
u e
u g
m u
q o
d c
u r
e b
o t
y k
h x
a o
h c
d w
m v
x x
d r
y r
l x
n m
q d
u t
w k
g a
l m
j e
u u
w k
i c
x b
b u
m u
n e
e m
a y
d t
m r
d y
a i
x j
o l
h g
q i
m f
h z
v l
h i
o j
v u
u s
o y
p y
y a
100
l u
e y
m i
o u
e t
z h
i r
c i
s f
p k
g g
b k
i b
z p
r z
u z
x c
m a
u l
f d
k y
r g
o u
z w
i g
o o
b o
p p
e l
l q
p w
a h
j p
a n
q d
d h
n c
w v
t d
j x
m b
p y
p p
a h
x u
s n
u p
g s
h d
i i
q x
b m
j f
j x
v c
d u
s j
y u
b i
e y
m b
s w
q i
o y
g y
x y
m y
e z
y v
z p
j v
g e
b e
o e
f c
f u
s t
d x
x i
i t
s g
e i
h e
c k
z h
f d
i l
r l
q j
n f
z x
q t
s r
b v
p s
y k
s h
n e
p b
k p
100
t q
d p
b d
o u
b t
q b
w c
v i
f r
j x
j u
d j
n d
g t
i e
v q
g d
i a
v j
c w
a y
b u
e w
p w
v j
g y
h e
j l
e x
b p
i p
u w
z q
z d
b u
u d
z b
a v
s f
q p
q p
u w
i z
w f
v o
d y
w d
v y
b v
r u
z c
g m
j y
f g
x d
t v
u n
n n
s e
s l
l p
u w
u i
f p
l x
b z
n k
k h
p w
a p
l n
c t
i f
j r
d c
s d
z o
y o
e v
u g
f r
c w
f s
o m
e x
m q
j r
w o
g r
w h
k l
b o
e m
h a
g k
c c
a n
h e
s h
e v
100
m y
p q
h x
r l
u n
y n
d f
r z
b h
s a
e j
y u
a g
o f
b u
t u
n p
m i
w u
j f
s q
x j
k v
d q
r o
x x
r v
c w
d t
n s
o e
v g
p b
x k
p l
d g
r i
f b
r c
q i
f i
g p
n y
r k
e r
x f
n s
u v
f c
p t
c w
g t
w t
x m
u n
y p
f c
c g
q u
n u
b u
m l
i o
t i
c n
l k
f e
z s
e b
r x
m a
e p
v t
q h
d n
j d
q e
u v
g y
n p
a k
q z
r f
j p
o v
x a
p d
w c
j m
b o
s m
s k
f k
j o
e n
x w
x g
n n
f o
l w
100
w t
w j
n n
b v
j w
k c
m d
o e
u u
h z
v y
g h
w v
j u
q b
x x
i p
c t
o v
r g
i a
d d
h v
r r
s d
c y
h q
l k
e e
h w
t x
m e
a b
w q
w q
q p
s h
e u
n b
f v
v g
w j
v d
j j
f a
z q
x z
c l
d x
n z
q c
j g
a l
o p
k p
x v
g f
i v
e c
c t
k m
l b
o j
g p
q t
v v
b h
s g
v d
v i
e h
n s
q k
m x
r w
i q
r d
m v
l h
b u
r b
k y
h t
y e
n e
m t
o r
d b
y e
c q
g r
u l
i a
h i
e v
x i
j w
r j
o q
u p
100
j b
u g
h x
d x
p i
z f
s w
y w
g b
y f
q l
j v
h z
r a
r v
y l
u a
z u
r d
n c
k j
h p
l c
f f
k r
e e
b c
d p
p i
f u
i h
j d
x c
h j
n r
c x
m x
c j
o x
q h
n a
d x
m r
z g
b e
n h
m l
p w
h m
d w
t v
s h
q f
e u
e e
g x
u r
i j
s g
m k
r v
g z
w f
r v
t f
a w
d p
u t
p t
z b
y t
n g
r s
a x
j j
g n
o c
i m
j k
s z
w d
s s
n z
v o
r d
y u
c p
j n
l u
f k
z u
x m
a n
a f
e m
p s
k c
c j
z a
d x
100
t r
g d
r y
s q
c c
y z
n b
q v
c q
c q
i j
l t
c v
v n
m b
s a
d i
g z
r w
a a
z t
w z
w p
f m
f b
k j
c n
k v
l e
h h
j z
h c
d p
l n
n u
p m
n p
g l
z j
k n
w e
u w
s y
e g
o f
e n
p x
m m
b s
o a
m p
g d
q z
k m
z q
u x
t v
v q
x n
s b
q l
k z
l g
a z
z m
d p
s n
o j
v l
b y
x w
t x
q t
g o
r n
a b
a i
q k
l l
z s
h k
z f
o c
n n
o m
k q
p l
e e
s f
s n
o m
w u
h q
d o
g s
f c
h o
s e
s y
m h
100
x g
t w
a o
u y
n v
j o
j d
t f
t q
k w
a b
r p
u i
i j
q m
s w
s p
g l
l v
s c
q a
d b
g b
t w
s b
e e
t t
d w
f n
b n
j y
p v
j d
y x
z u
x q
t s
t a
z b
c p
t t
o h
f o
e r
g m
k f
b r
v c
z k
g v
o b
t f
g h
j o
d h
a n
w y
n p
i b
o t
a r
i a
e b
n d
z e
f w
d p
w a
o l
s h
v s
q t
k t
v f
y s
j l
l z
c u
x q
w s
q y
n d
d t
f m
t r
l z
s q
k e
j e
z h
s k
l k
e f
x p
h c
c v
y z
v s
g d
x c
100
b b
s i
m w
a e
l y
i z
k f
m t
i o
s k
f s
t x
p g
j o
q x
y i
r s
q s
w f
d q
q j
q n
g c
q d
n r
l l
i u
a e
v z
w m
u n
f u
n n
v x
o l
v y
m g
i l
q u
n a
l d
a y
f v
u a
o a
n s
n l
a v
s c
p v
u i
o m
a i
c w
x q
w s
q k
g w
y x
z a
t n
a n
k i
m a
y e
n b
q u
c b
a q
g g
a x
h c
y r
q n
q x
m q
f l
t o
q p
v h
k o
i i
m a
q m
v m
j x
b v
o s
i a
z f
x y
j n
b c
r e
n r
i m
x x
y s
h j
v o

AC output:

Code: Select all

jtpedersen · Post by **jtpedersen** » Sat Mar 01, 2014 12:26 am

I am quite certain that i have solved it, with help from the test cases here.

But I keep getting runtime errors that i am not able to reproduce, i think it may be something very obvious.

Can you spot the error?
https://gist.github.com/jtpedersen/80c0c437c84aa1d7bb4e

EDIT fixed the mistake, stupid mistake where i forgot to return a value, and C++ apparently did not mind and just used some value that worked anyway on my machine. From now on it is

Code: Select all

-Wall -Werror -pedantic

on every thing !

Rafiq123 · Post by **Rafiq123** » Sun Jun 29, 2014 7:25 pm

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int par[100005];
void makeset(int element)
{
par[element]=element;
}
int find_rep(int r);
void Union(int a,int b)
{
int u,v;
u = find_rep(a);
v = find_rep(b);
if(u!=v)
{
par=v;
}
}

int find_rep(int r) /// find representitive.
{
if(par[r]==r) return r;
else
{
return par[r]=find_rep(par[r]);
}
}
int main()
{
map<string,int>M;
int i,n,index1,t,test,count,frnd,top,x;
string name_1,name_2;

cin>>test;
for(t=1; t<=test; t++)
{
vector<int>U;
vector<int>V;
top = 1;
count=0;
cin>>frnd;
for(i=1; i<=frnd; i++)
{
cin>>name_1>>name_2;
if(!M[name_1])
{
M[name_1]=top++;
makeset(M[name_1]);
}
if(!M[name_2])
{
M[name_2]=top++;
makeset(M[name_2]);
}

Union(M[name_1],M[name_2]);
x = M[name_1];
U.push_back(M[name_1]);
V.push_back(M[name_2]);

for(n=0; n<U.size(); n++)
{
Union(U[n],V[n]);
}

for(index1=1; par[index1]>0; index1++)
{

if(par[x]==par[index1])
count++;

}
cout<<count<<endl;
count=0;

}
memset(par,0,sizeof(par));
M.clear();
}
return 0;
}

Rafiq123 · Post by **Rafiq123** » Sun Jun 29, 2014 8:43 pm

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int par[100005];
void makeset(int element)
{
par[element]=element;
}
int find_rep(int r);
void Union(int a,int b)
{
int u,v;
u = find_rep(a);
v = find_rep(b);
if(u!=v)
{
par=v;
}
}

int find_rep(int r) /// find representitive.
{
if(par[r]==r) return r;
else
{
return par[r]=find_rep(par[r]);
}
}
int main()
{
map<string,int>M;
int i,n,index1,t,test,count,frnd,top,x;
string name_1,name_2;

cin>>test;
for(t=1; t<=test; t++)
{
vector<int>U;
vector<int>V;
top = 1;
count=0;
cin>>frnd;
for(i=1; i<=frnd; i++)
{
cin>>name_1>>name_2;
if(!M[name_1])
{
M[name_1]=top++;
makeset(M[name_1]);
}
if(!M[name_2])
{
M[name_2]=top++;
makeset(M[name_2]);
}

Union(M[name_1],M[name_2]);
x = M[name_1];
U.push_back(M[name_1]);
V.push_back(M[name_2]);

for(n=0; n<U.size(); n++)
{
Union(U[n],V[n]);
}

for(index1=1; par[index1]>0; index1++)
{

if(par[x]==par[index1])
count++;

}
cout<<count<<endl;
count=0;

}
memset(par,0,sizeof(par));
M.clear();
}
return 0;
}

OJ Board

11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

Re: 11503 - Virtual Friends

11503 - Virtual Friends....TLE ....please help....

11503 - Virtual Friends