**Hi. A few days ago I have solved a Problem on UVa named Virtual Friends .
The link is here : Click Here .
This is a Union Find / Disjoint Set Find problem . I used that algorithm and Got Accepted verdict at 2.281 Sec. Although the problem says it's Time Limit is 10 Sec. May be the data set is Huge. I have seen the Best Submission ever for this problem is 0.104 Sec.
Now my Question is how to decrease my Run Time?? I want to get Accepted verdict less than 1 Sec. How to optimize my Code ??
My Code is : http://ideone.com/34YqH9
Thanks is Advance.**
You could try to use fast I/O.
How ?? Sorry I didn't get your point ... Can you please explain ...
You are using "cin" to read strings, it's very slow to read anything. It's better to use scanf instead of cin to reduce the runtime. You can also use "gets" to read string, it's faster than scanf. Take a look at: http://abhisharlives.blogspot.com.br/2012/06/really-fast-io-methods-for-programming.html
You can hash the string instead of putting it into a map.
How can I do that ??
I have changed your code to use scanf to read the strings http://ideone.com/MXXktl Result: 0.760 s (-1.521 s)
I have also tried to use hash table instead of map http://ideone.com/4qQZ1m Result: 1.624 s (-0.657 s)
Two techniques combined: http://ideone.com/nROrJK Result: 0.257 s (-2.024 s)
Thanks Sir.. it Really Worked ... But I didn't get you Hashing Function. Whats the idea behind Hashing ?microtony
It converts a string into an integer of small range (here: 0-599999) Two equal strings should give the same integer while two different strings should hopefully give two different integers (collisions may occur but the hash function takes account of that (open addressing + linear probing)
Read more here: https://en.wikipedia.org/wiki/Hash_table
Note that in my code the choice of 23 is not very good you should try another larger prime number.