11503 - Virtual Friends

[aybek]

Rafiq123, explain your code. And take it into code area with tags.
Try to use sets not map

[brianfry713]

Don't double post.

[brianfry713]

Try using scanf and printf instead of cin and cout.

[vector9x]

You are counting for the number of elements in the set after each query... that is not efficient.
You can hold an array num_elements[N] which contains the number of elements of each set (initially 1).
When you make the union, you can do something like:

Code: Select all

...
if(u!=v)
{
    par[u]=v;
    num_elements[v] += num_elements[u];
}

then, you can get the number of elements in constant time with num_elements[find(M[name_1])]
or even better, your union function could return that value.

[ssavi]

Hi I have solved 11503 ...
Here is my Code : http://ideone.com/34YqH9
But I need to optimize this Code .. I got AC with 2.281sec. But I want to get AC within 1 sec.
Although Time Limit : 10 sec...
How to optimize it ?

Thanks in Advance.