## 10608 - Friends

Moderator: Board moderators

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

### 10608 - Friends

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

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### DFS

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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

### Set & Disjoint set method

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.
"Everything should be made simple, but not always simpler"

gawry
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
I am sorry, i have written wrong.
"Everything should be made simple, but not always simpler"

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal
thanks you guys.. .I didn't remember using union find... i'll try it.
be cool...

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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
"Everything should be made simple, but not always simpler"

PdR
New poster
Posts: 24
Joined: Mon Dec 30, 2002 4:27 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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### 10608

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.
Last edited by Eduard on Wed Aug 11, 2004 9:26 pm, edited 1 time in total.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
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

someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Hi,
If you know C++ STL, you can use <vector> to store the adjacency list.
Then apply plain and simple DFS

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
I made some changes on my algo and got.
10583 ---> AC(1.012sc)
10608 ---> AC(0.227sc);
10685 ---> TLE
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

dispanser
New poster
Posts: 18
Joined: Wed May 01, 2002 4:12 pm
Location: Jena/Germany
Contact:
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.