## 10608 - Friends

**Moderator:** Board moderators

### 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.

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.

### 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.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"

### 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.

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

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

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]

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"?

10583: TLE

10608: AC 1.190sc

10685: TLE

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

someone who like to solve informatic problems.

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

I made some changes on my algo and got.

10583 ---> AC(1.012sc)

10608 ---> AC(0.227sc);

10685 ---> TLE

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

http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

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;
}
}
```

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