10608

playerX · Post by **playerX** » Wed Feb 18, 2004 12:18 am

Is there any mehod better than bfs to solve this prob?

shamim · Post by **shamim** » Wed Feb 18, 2004 5:46 am

Well i solved using DFS and i had poor timing and memory usage. A lot of guys were more efficient in both of these respect.

I have used <vector> to make the adjacency list, but the traversal was quite trivial. Still i had poor timing.

I wonder if there is a better algorithm to solve this problem.

anupam · Post by **anupam** » Wed Feb 18, 2004 8:40 am

You can use Set and disjoint set method with path compression (which brings O(n^2) to O(n))
with find and union.
It should be first.
At least I have solved the problem during the contest by that way.
Hope it helps.
Hint: CRLS and Sahni.

gawry · Post by **gawry** » Wed Feb 18, 2004 9:53 pm

I don't know how you want to get O(n) complexity with union-find. As far as I know it will be rather O(m\alpha(m,n)).

anupam · Post by **anupam** » Thu Feb 19, 2004 5:45 pm

I am sorry, i have written wrong.

playerX · Post by **playerX** » Sat Feb 21, 2004 12:08 am

thanks you guys.. .I didn't remember using union find... i'll try it.

jpfarias · Post by **jpfarias** » Fri Apr 02, 2004 2:50 pm

Are there more than 1 case on the input?

The input description says the first line will be N and M, but the example shows that the first line is the number of cases.

Which is correct?

I'm getting sigsegv when I use the first line as the number of cases, and WA when I use it as N and M.

JP.

anupam · Post by **anupam** » Fri Apr 02, 2004 5:47 pm

The first line is the number of cases and the second line conains N & M following M lines and again N & M and M lines and so on.
The problem statement was confusing..
----
Anupam

PdR · Post by **PdR** » Sun Apr 04, 2004 12:46 am

The input has to have some garbage appended to it:
When I simply ignored (but still reading it) the first number and solved for each n and m in the input I've got WA, when I stopped after say k blocks (being the first integer) on input I got AC.

Eduard · Post by **Eduard** » Mon Aug 09, 2004 11:06 am

Can somebody explain me algoritm to solve this problem I'm getting TLE.
How I know the algoritm Union Find can solve this problem but i don't know that algo.Please explain me that algo or another algorithm which can solve this probelm.Thay are some other problems which are similiar to this(10685,10583).Please tell me algo to solve this problems.

Minilek · Post by **Minilek** » Mon Aug 09, 2004 2:00 pm

There are two good ways I know of doing it. Both involve the same algorithm, but different data structures to represent sets.

First data structure is linked list, but modified so that each element also has a pointer to the "root" (which will be the representative for the set).
So whenever you start a new input set, intialize n linked lists each with root pointing to themself and "next" pointing to NULL. Whenever you get an input telling you a pair of friends, you merge the two linked lists that represent the two sets (or do nothing if they are already in the same set). tack on the smaller linked list to the bigger and update the root for every element in the smaller linked list (this way you get m + nlgn time instead of mn). actually, tacking on requires your linked list structure to also keep an "end" pointer to the end of the list for efficiency, but this is not needed. just splice the 2nd list into the first one (it saved me both memory and time ^^)

i used the method above for .164s

there is a faster method which grows like m*(inverse_ackermann_function(n)) but it is more code to implement than the above, so i have not done it yet. if u want to find out more about this way (it uses disjoint-set forests as a data structure), google it or read CLRS

[EDIT]
Contrary to what I believed before, it isn't more code to implement
the disjoint-set forest structure. I just implemented it and submitted.
I used less memory than the linked list way, but it was .012s slower for some reason (AC in .174). I guess the inputs are nice enough so that
the m + nlgn worst case of the linked-list implementation does not occur ?
(and yes, i implemented both path-compression and union-by-rank heuristics)
[/EDIT]

[EDIT2]
Just to see, I submitted a version of my implementation that uses the REVERSE of the union-by-rank heuristic and only lost .004 seconds. Not implementing path-compression also only lost me .05 seconds or so. I guess the data must be very friendly : )
[/EDIT2]

Eduard · Post by **Eduard** » Wed Aug 11, 2004 9:24 pm

I don't know how good I understand your algo,but finaly find one, similiar to what you explain and got
10583: TLE
10608: AC 1.190sc
10685: TLE

In your algorithm can you tell me what is "link"?

shamim · Post by **shamim** » Fri Aug 13, 2004 12:12 pm

Hi,
If you know C++ STL, you can use <vector> to store the adjacency list.
Then apply plain and simple DFS

Eduard · Post by **Eduard** » Thu Aug 19, 2004 6:28 pm

I made some changes on my algo and got.
10583 ---> AC(1.012sc)
10608 ---> AC(0.227sc);
10685 ---> TLE

dispanser · Post by **dispanser** » Sat Sep 04, 2004 2:44 pm

the following code ends with a sigsegv. it's just reading the input.
TC refers to the number of testcases, nC is the number of citizen, nP is the number of Pairs of input. i can't see a flaw in it.

i know a adjacency matrix is not clever and will give TLE, but at least it should not fail!

Code: Select all

	while(TC--) {
			
		cin >> nC >> nP;
		bool fr[nC+1][nC+1];
		REP(i, nC+1) REP(j, nC+1) fr[i][j] = false;	// OK
		REP(i, nP) {	//	for each input pair
			cin >> t1 >> t2;	//	read the values from stdin
			fr[t1][t2]	=	true;	//	mark t1 and t2 as friends
			fr[t2][t1]	=	true;
		}
        }

any help on the subject is appreciated. could it be that the input is messed up, and if yes, how are you reading it?

EDIT: i just noticed that for 30k citizen, the current scenario would need too much memory, so don't bother answering.

OJ Board

10608 - Friends

10608 - Friends

DFS

Set & Disjoint set method