10034 - Freckles

Observer · Post by **Observer** » Thu Jun 12, 2003 4:15 am

I'm a beginner in MST.

Could anyone give my some test cases for this problem. I keep getting WA......

Thx in advance!

Observer · Post by **Observer** » Thu Jun 12, 2003 6:52 am

Finally I've got an AC...

However, I think my algorithm is too slow......

I use Kruskal's algorithm, however, I don't know how to check wheter the two endpoints of each line are disconnected effectively......

So, can anyone help me?? Thx!!

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Jun 12, 2003 8:02 am

Union-find algorithm

DM

Observer · Post by **Observer** » Thu Jun 12, 2003 9:51 am

Could you give me more details, plz?

I often used Adjacency Matrix to solve graph problems, but it seems slow......

Dominik Michniewski · Thu Jun 12, 2003 11:55 am

try on google

idea is simple :
1. create vector of such number of elements (or table) of graph (nodes)
2. initialize all elements to our number (i.e. 1,2,3 .... for node 1,2,3 ...)
3, for each added edge update values in such way, that to groups of nodes, which are separate earlier join in one group

example:
nodes 1,2,3,4,5
edges 12,14,53
table: 1,2,3,4,5
step 3. edge 12 table (after) : 1,1,3,4,5
step 3. edge 14 table (after) : 1,1,3,1,5
step 3. edge 53 table (after) : 1,1,3,1,3
and so on

time complexity is O(E*V) and is better than using adjacency matrix which is typical O(V^3)

Best regards
DM

Observer · Post by **Observer** » Thu Jun 12, 2003 1:19 pm

Thx for your help!

However, I still don't quite get it.....

I tried to search Google for related information. However, most of it is uninterpretable by me...... >_<

Can anyone explain it more clearly plz?? Any help is appreciated!

Observer · Post by **Observer** » Thu Jun 12, 2003 1:50 pm

(Edited)

Plz see if what you mean is as follows, Dominik:

Let every edge be X -> Y, where X > Y.

Step 1: Initialization
- Then we have the following array: 1 2 3 4 5 ...

Step 2:
For each edge do \\ for MST, check if array[X] <> array[Y]
- for each node do
-- if array[node] == array[X]
--- then array[node] = array[Y]

Step 3:
All edge is connected when every cell of the array is 1.

Is it correct? Plz reply. Thx!

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Jun 12, 2003 2:54 pm

No.

let edge X->Y, you cannot make any assumption to x and y. our goal is making equal values in table.

so.
if table[x] != table[y] <- that means group of nodes to which belongs x is different of group of nodes to which belongs y />
let z = table[x]
change every table[x] == z to table[y]

after step 2, we have number of groups (disjoint) ...

DM

Observer · Post by **Observer** » Fri Jun 13, 2003 2:55 am

Thx!! With your help, I've got accepted in much shorter time!!!

However, I'm still getting WA in Q10397......

Anyway, Thx a lot!!

Btw, any help on that one too? Thx!

Towhid · Post by **Towhid** » Sun Jun 29, 2003 1:59 pm

Can someone provide an critical input set for the problem?

titid_gede · Post by **titid_gede** » Sun Jun 29, 2003 2:33 pm

i dont have any critical inputs, but i can give you a hint, since i think your problem's same than mine...
hint : only use sqrt when necessary.. do not use sqrt if you can avoid it. hope it can help.

-titid-

b3yours3lf · Post by **b3yours3lf** » Wed Oct 22, 2003 7:14 am

i use kruskal to solve this problem, but a got WA many times...

titid_gede · Post by **titid_gede** » Wed Oct 22, 2003 8:27 am

hmmm... you dont even pass the sample input output

at first look, your sort function seems to be incorrect

b3yours3lf · Post by **b3yours3lf** » Wed Oct 22, 2003 10:03 am

sorry, i've post wrong code, here is the correct one
[c]
--cut--
[/c]

Grinder · Post by **Grinder** » Sat Oct 25, 2003 2:43 pm

b3yours3lf u will edit this.

for(k=0;k<n;k++)
{
if(set[k]==set[e[j].v2])
set[k]=set[e[j].v1];
}

as

for(k=0;k<n;k++)
{
if(set[k]==set[e[j].v1)
set[k]=set[e[j].v2];
}

may be u will got AC

OJ Board

10034 - Freckles

10034 Help!

10034 input

10034 - Freckles