Ankur's Blog

let's start Code

Showing posts with label DSU. Show all posts
Showing posts with label DSU. Show all posts

793 - Network Connections

, , No comments

793 - Network Connections

Topic : DSU

Solution 01:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;

#define INF 1<<30
#define MAX 10005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int parent[MAX];

void Initialization(int n)
{
  for(int i = 0; i <= n; i++)
    parent[i] = i;
}

int find_parent(int x)
{
  if(parent[x] == x)
    {
        return x;
    }
  return parent[x] = find_parent(parent[x]);
}

void make_union(int x, int  y)
{
  parent[find_parent(x)] = find_parent(y);
  //parent[find_parent(y)] = find_parent(x);
}

bool isUnion(int x, int y)
{
  return find_parent(x) == find_parent(y);
}

int main()
{
    //FASTIO
    ///*
    //double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
   #endif
    //*/

    int t;
    cin >> t;
    bool space = false;
    for(int cs = 0; cs < t; cs++, space = true){
      Initialization(MAX);
      if(space)cout << endl;
        int N;
        cin >> N;
        getchar();
        int yes = 0, no = 0;
           string str;
            int x,y;
        while(getline(cin, str)){
          if(str == "")break;
          char ch;
          stringstream S(str);
         // S >> ch;
          S >> ch >>x >> y;
            if(ch == 'c'){
                make_union(x,y);
            }
            else{
                //cerr << parent[x] << " "<<parent[y]<<endl;
                if(isUnion(x,y))yes++;
                else no++;
            }
        }
        cout << yes << ","<<no<<endl;
    }


      //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   return 0;
}

Share:
Read More

Merging Communities

, , No comments

Merging Communities

Topic: DSU

Solution 01:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int parent[MAX*2], Rank[MAX];

void Initialization(int n)
{
  for(int i = 0; i <= n; i++)
    parent[i] = i, Rank[i] = 1;
}

int find_parent(int x)
{
  if(parent[x] == x)
    {
        return x;
    }
  return parent[x] = find_parent(parent[x]);
}

void make_union(int x, int  y)
{
    int p = find_parent(x);
    int q = find_parent(y);
    if(p != q){
        if(Rank[p] < Rank[q])
            swap(p,q);
        parent[q] = p;
        Rank[p] += Rank[q];
    }
}

bool isUnion(int x, int y)
{
  return find_parent(x) == find_parent(y);
}

int main()
{
    //FASTIO
    /*
    //double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
   #endif
    //*/
        int N,Q;
        cin >> N >> Q;
        Initialization(N);
        int cnt = 1;
        map<string, int> mp;
        for(int i = 1; i <= Q; i++){
            int x,y;
            char ch;
            cin >> ch;
            if(ch == 'M'){
                cin >> x >> y;
                make_union(x,y);
            }
            else{
                cin >>x;
            cout << Rank[find_parent(x)]<<endl;
        }
            //cerr << Rank[find_parent(x)] << " " <<Rank[find_parent(y)]<<endl;
        }

      //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   return 0;
}


Another Solution

Share:
Read More

Disjoint Set Union

, , No comments
Share:
Read More

11503 - Virtual Friends

, , , No comments

11503 - Virtual Friends

Topic: DSU

solution 01:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int parent[MAX*2], Rank[MAX];

void Initialization()
{
  for(int i = 0; i <= MAX; i++)
    parent[i] = i, Rank[i] = 1;
}

int find_parent(int x)
{
  if(parent[x] == x)
    {
        return x;
    }
  return parent[x] = find_parent(parent[x]);
}

void make_union(int x, int  y)
{
    int p = find_parent(x);
    int q = find_parent(y);
    if(p != q){
        if(Rank[p] < Rank[q])
            swap(p,q);
        parent[q] = p;
        Rank[p] += Rank[q];
    }
}

bool isUnion(int x, int y)
{
  return find_parent(x) == find_parent(y);
}

int main()
{
    //FASTIO
    /*
    //double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
   #endif
    //*/

    int t;
    cin >> t;
    while(t--){
        Initialization();
        int F;
        cin >> F;
        int cnt = 1;
        map<string, int> mp;
        map<int, int>res;
        map<int,int>visit,ans;
        for(int i = 1; i <= F; i++){
            string s1,s2;
            cin >> s1 >> s2;
            if(mp[s1] == 0)mp[s1] = cnt++;
            if(mp[s2] == 0)mp[s2] = cnt++;
            int x = mp[s1];
            int y = mp[s2];
            make_union(x,y);
            cout << Rank[find_parent(x)]<<endl;
            //cerr << Rank[find_parent(x)] << " " <<Rank[find_parent(y)]<<endl;
        }
    }

      //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   return 0;
}

Share:
Read More

About

let's start CODE

Popular Posts

  • E-maxx training part - 01
                             Binary Exponentiation 1230 - MODEX              Solution 11029 - Leading and Trailing      Solution I...
  • 11029 - Leading and Trailing
    11029 - Leading and Trailing  Topic: Binary Exponentiation  
  • A - Frog 1
    A - Frog 1 Solution 01: IH19980412 //copy 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2...