A problem is that this is a directed graph. With kruskal algorithm, the case
may be that a node in the result has multiple parents.
Best Regards,
Hongzhi Wang
- Original Message -
From: "Siva" <[EMAIL PROTECTED]>
To: "Algorithm Geeks"
Sent: Wednesday, August 02, 2006 10:33 PM
Subject: [
On 8/1/06, sathiya narayanan <[EMAIL PROTECTED]> wrote:
>
> Given: 2 Arrays of N and M numbers in size.
> We have to find how many common numbers are available ?
>
> Eg: A={8,5,4,2,9}
> B={1,2,3,4,6)
>
> Solution is:2
> Common elements are {2,4}
>
> What i wll do is Sort the array A and the
If you know the range of numbers say 0 to L and there are no repetitions (this is just for convenience)take a bitvector B of size LcommonCount := 0for (i, j) in M, N if(i == j) //direct hit B[i] = 1
commonCount++ else if(B[i] = 1 AND B[j] = 1) commonCount += 2 else if(B[i] = 1) //j
If you know the range of numbers, you can allocate an array of that size, and ...
are you satisfied with this?!!!
On 8/2/06, sathiya narayanan <[EMAIL PROTECTED]> wrote:
yup thanx, is there any way other than hashing ? which should be better than O(nlgn)
, 133470973390.236450, 270};int main(){m[2
Siva wrote:
> Max spanning forest is not NP hardu can write a simple kruskal
> algorithm that runs in )(E log* V) for thisas u can see it is
> definitely polynomial unlike longest path problem
>
> Siva
Or u can write Prim's algorithm which has the same complexity. But for
some graphs it
yup thanx, is there any way other than hashing ? which should be better than O(nlgn)
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups
Max spanning forest is not NP hardu can write a simple kruskal
algorithm that runs in )(E log* V) for thisas u can see it is
definitely polynomial unlike longest path problem
Siva
--~--~-~--~~~---~--~~
You received this message because you are subscribed
I've been using Google Talk and thought you might like to try it out.
We can use it to call each other for free over the internet. Here's an
invitation to download Google Talk. Give it a try!
---
Kim Sewon wants to stay in bette
