fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. #include <cctype>
  7. #include <stack>
  8. #include <queue>
  9. #include <list>
  10. #include <vector>
  11. #include <map>
  12. #include <sstream>
  13. #include <utility>
  14. #include <set>
  15. #include <math.h>
  16.  
  17. using namespace std;
  18. map<string, int> m;
  19. int size[100000] = {0};
  20. int parent[100000];
  21.  
  22. int find_parent(int x) {
  23.     if (parent[x] == x) {
  24.         return x;
  25.     } else {
  26.         parent[x] = parent[parent[x]];// applying path compression
  27.         return find_parent(parent[x]);
  28.     }
  29. }
  30.  
  31. void do_union(int x, int y) {
  32.     int i, j;
  33.     for (i = x; parent[i] != i; i = parent[i]) {
  34.         parent[i] = parent[parent[i]];// applying path compression
  35.     }
  36.     for (j = y; parent[j] != j; j = parent[j]) {
  37.         parent[j] = parent[parent[j]];// applying path compression
  38.     }
  39.     if (size[i] > size[j]) {// adding the smaller set to the larger set
  40.         size[i] += size[j];// adding the smaller set's size to the larger set's size
  41.         parent[j] = parent[i];// adjusting the parent pointer 
  42.         printf("%d\n", size[i]);// displaying the size of the new set formed
  43.     } else {
  44.         size[j] += size[i];
  45.         parent[i] = parent[j];
  46.         printf("%d\n", size[j]);
  47.     }
  48. }
  49.  
  50. int main() {
  51.     string f1, f2;
  52.     int t, n;
  53.     scanf("%d", &t); // taking test cases
  54.     while (t--) {
  55.         int index = 1;
  56.         m.clear();
  57.         memset(size, 0, sizeof (size));
  58.         scanf("%d", &n); // taking no of friend pairs
  59.         while (n--) {
  60.             cin >> f1 >> f2; // taking friend pair
  61.             if (!m[f1]) {// if  friend1 doesn't exist, put f1 in the map 
  62.                 m[f1] = index;
  63.                 parent[m[f1]] = index++;// f1 is its own parent initially
  64.                 size[m[f1]]++;
  65.             }
  66.             if (!m[f2]) {// if  friend1 doesn't exist, put f2 in the map
  67.                 m[f2] = index;
  68.                 parent[m[f2]] = index++;// f2 is its own parent initially
  69.                 size[m[f2]]++;
  70.             }
  71.             if (find_parent(m[f1]) != find_parent(m[f2]))// if they belong to different sets print the size of the set formed after theit union
  72.                 do_union(m[f1], m[f2]);
  73.             else// else print the size of the current set
  74.                 printf("%d\n", size[parent[m[f1]]]);
  75.             /*/if (n > 0)
  76.                 printf("\n");*/
  77.         }
  78.         /*if(t>0)
  79.             printf("\n");*/
  80.     }
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0s 4220KB
comments (?)
stdin
copy 
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
stdout
copy 
2
2
1
2
2
2
3
2
3
4
3
2
3
2
4
4
6
5
9
15
18
20
21
21
21
21
21
21
22
22
2
2
2
3
4
3
4
2
5
3
9
10
5
15
15
16
16
17
17
2
19
19
20
21
22
22
23
24
24
24
2
2
3
2
4
2
3
2
4
4
5
6
4
8
9
13
14
5
15
15
15
15
16
16
16
17
17
17
22
23
2
2
2
2
3
2
4
4
5
6
2
2
6
8
8
3
4
10
3
11
12
15
23
23
23
24
25
25
25
25
2
2
2
2
4
2
5
2
4
2
3
5
6
4
10
5
11
12
13
14
6
8
22
22
22
22
22
22
22
22
2
2
2
3
2
3
2
2
4
4
5
4
5
9
11
12
13
17
17
17
18
18
3
18
18
19
22
22
22
22
2
2
2
3
4
5
2
2
2
6
4
3
3
9
5
6
7
16
17
17
17
21
21
21
21
21
21
22
22
23
1
2
3
2
3
4
2
2
5
2
4
6
7
8
12
12
12
12
13
14
14
3
15
4
17
21
23
24
25
25
2
2
2
2
2
2
4
3
3
1
5
2
2
7
2
10
13
13
3
14
3
15
18
19
19
19
19
20
22
22
2
2
3
4
2
3
2
2
3
5
9
9
10
4
11
15
16
17
3
18
18
21
21
21
22
23
23
23
23
23
https://ideone.com/evOPNK
11503 . version 2. added a new line at the end of output.
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!