Codevita Online Communities-Even Groups

Can anyone give me hint on how to solve this question?

1 Like

You can easily solve it using Disjoint-Set Data structure(using Union and Find procedures) . Its pretty straight forward . Remember to keep track of the number of nodes in each set . (Which is not that difficult !) .
For more reference : https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/ Hope this helps !

2 Likes

As already answered, this problems screams for a union-find data structure.
Another alternative when working with connected parts of a graph is to employ DFS.
When doing DFS, you already use an array for bookkeeping which vertex has already been visited.
In one run you will visit exactly the vertices in one component (counting during DFS will yield part of the result for the question).
Now start DFS not once but for each vertex that has not yet been visited (iterate over the array).
This yields the count for every component.

#include  <iostream>

#include  <algorithm>

#include <vector>

#include  <math.h>

using namespace std;

vector	<vector	<int	>> graph(1000000 + 1);

vector	<int> f_arr, s_arr;

vector	<char> flag_arr;

bool visited[1000000 + 1];

int n;

int solve_it(int num)

{

    int size = graph[num].size();

    int i;

    if (size == 0)

        return 0;

    int count = 0;

    for (i = 0; i < size; i++)

    {

        if (visited[graph[num][i]] == 0)

        {

            visited[graph[num][i]] = 1;

            count += solve_it(graph[num][i]);

        }

    }

    return 1 + count;

}

int dfs()

{

    fill(visited, visited + n + 1, 0);

    int count = 0;

    int i;

    int temp;

    for (i = 1; i <= n; i++)

    {

        if (visited[i] == 0)

        {

            visited[i] = 1;

            temp = solve_it(i);

            if (temp != 0 && (temp & 1) == 0)

            {

                count++;

            }

        }

    }

    return count;

}

int main()

{

    int i;

    int j;

    int ans;

    int mini;

    int temp;

    char ch;

    int count, size;

    cin >> n;

    i = 0;

    while (1)

    {

        cin >> ch;

        if (ch == '-')

            break;

        flag_arr.push_back(ch);

        cin >> temp;

        f_arr.push_back(temp);

        cin >> temp;

        s_arr.push_back(temp);

        i++;

    }

    size = i;

    for (i = 0; i < size; i++)

    {

        if (flag_arr[i] == 'C')

        {

            graph[f_arr[i]].push_back(s_arr[i]);

            graph[s_arr[i]].push_back((f_arr[i]));

        }

        else

        {

            count = dfs();

            cout << count << endl;

            ;

        }

    }

}