10034  Freckles
Moderator: Board moderators
10034 Help!
I'm a beginner in MST.
Could anyone give my some test cases for this problem. I keep getting WA......
Thx in advance!
Could anyone give my some test cases for this problem. I keep getting WA......
Thx in advance!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
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!!
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!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Could you give me more details, plz?
I often used Adjacency Matrix to solve graph problems, but it seems slow......
I often used Adjacency Matrix to solve graph problems, but it seems slow......
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
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
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
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!
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!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
(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!
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!
Last edited by Observer on Thu Jun 12, 2003 5:46 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
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
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
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!
However, I'm still getting WA in Q10397......
Anyway, Thx a lot!!
Btw, any help on that one too? Thx!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut

 New poster
 Posts: 44
 Joined: Wed Aug 14, 2002 3:02 am
10034  Freckles
i use kruskal to solve this problem, but a got WA many times...
Last edited by b3yours3lf on Wed Oct 22, 2003 10:05 am, edited 1 time in total.

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut

 New poster
 Posts: 44
 Joined: Wed Aug 14, 2002 3:02 am
sorry, i've post wrong code, here is the correct one
[c]
cut
[/c]
[c]
cut
[/c]
Last edited by b3yours3lf on Mon Oct 27, 2003 5:42 am, edited 1 time in total.