A program which is difficult

Question

This is my first post in csstack exchange, and I don't know if this type of questions can be posted here.

So I have been trying this problem for 3 days and I got a solution but it fails for the hidden test cases.

Question:

There is a village festival happening in which several group of relatives meet every year. Each person is allocated an identifier which is a positive integer.N pairs of relatives identifiers are passed as input.

Then finally given a person's identifier I, the program must print the count of the relatives C in the group of the person with the identifier I.

Input Format: The first line contains the values of N. N lines contain the identifiers of two persons who are related. The next line (N+2)th line, will contain the identifier I of the person for whom the relative count of his group is to be printed.

Output Format: The first line will contain the count of relatives C in the group of the person with identifier I.

Boundary Conditions: 1 <= N <= 100001 <= I <= 1000000

Example Input/Output 1: Input:

Output:4

Explanation:

10, 20, 30, 40 form a relative group. 55, 35, 22 form another relative group. So the count of relatives for the person with identifier 40 is 4.

The method I approached was:

for(auto i = v.begin() ; i!=v.end();i++)
{
    if(i->first == r || i->second == r)
        {
            count+=2;
            if(i->first == r)
            r = i->second;
            else
            r = i->first;
            remove(v.begin(),v.end(),*i);
            n--;
            break;
        }
}

for(int i =0;i<n;i++)
{
    for(int j =0;j<n;j++)
    {
        if(r == v[j].first || r == v[j].second)
            {
                if(r == v[j].first)
                    r = v[j].second;
                else
                    r = v[j].first;

                count++;
                remove(v.begin(),v.end(),v[j]);
                n--;
            }
    }
}

cout<<count;

So what's the correct solution to this problem?

`"this is my first post in csstack exchange, and i don't know if this type of questions can be posted here."` - check out https://stackoverflow.com/help/on-topic and everything else in https://stackoverflow.com/help — chickity china chinese chicken, Jul 12 '17 at 00:13
In particular, consider reading [this](https://stackoverflow.com/help/asking) part of help center. Cheers! — iehrlich, Jul 12 '17 at 00:14
The first thing that jumps to ones mind is to create a graph structure and then do Breadth First Search to find the connected component of an identifier. Although in this case, Union Find might be better. — Aziuth, Jul 12 '17 at 00:20
Take a look at one of these [C++ books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Ron, Jul 12 '17 at 00:21
Please give your question a title which clearly describes the problem. — m69's been on strike for years, Jul 12 '17 at 00:21
what you can post here is a complete program (or a reasonably self contained section of one) that is not working for reasons you dont understand. What you have posted is not OK. what is `v`, what does `remove` do? etc — pm100, Jul 12 '17 at 00:23
@Aziuth i think a list of sets will do. for each input pair look to see if either is in anyone of the sets and if so add the other member to the set — pm100, Jul 12 '17 at 00:25
Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. — Prune, Jul 12 '17 at 00:33
Debugger. Use a debugger. A debugger will allow you to separately execute each statement, *watching* values of variables. Please edit your post with the results of your debugging sessions. Also, drawing out your graph or list while debugger is a good idea. — Thomas Matthews, Jul 12 '17 at 01:26
@aschepler If this significantly lowers the implementation effort - I could live with this... — Scheff's Cat, Jul 12 '17 at 06:17

Aziuth · Accepted Answer · 2017-07-12T15:32:34.310

Essentially, your question is this: given a graph with nodes represented as indices and edges as index pairs, and given an index i that represents a node, find all nodes which are connected to the given node.

UnionFind algorithm to find connected components over nodes with indices:

Initialize an array father of size number of nodes, with father[i] = i

for each edge e consisting of two indices i, j:
    ind = i
    while(ind != father[ind]) ind = father[ind]
    father[j] = ind

for each entry i of the array:
    replace father[i] by father[father[i]] until those are equal

After that, all nodes in the same component have the same father. You do that with your data, and then, for a given index i, find all other indices j with father[i] = father[j].

(slight improvement in run time: after ind is set to it's final value, update the father of i and its father and so on to the value ind)

Short explanation of UnionFind: it creates a tree in which only index pointers to the father of a node is stored (requires only an array). This is done by iterating over the edges. For every edge, the father of one of the incident nodes is set to the highest ancestor of the other node. Essentially, we start with a forest of single nodes and assemble them to trees. At the end, we change the remaining trees so that all leaves are direct children of the root.

Since in your example some numbers are missing, you might want to create some table that translates your input index to a range of numbers which are actually used. However, if we are talking about a small maximum index, like under one thousand, it won't really hurt not to do it.

A program which is difficult

1 Answers1