Converting an adjacency list into partitioning..help needed

[Karthik]

HI guys,

I have encountered a problem on converting an adjacency matrix
into partitioning. By partitioning, I mean that they are a collection
of lists in which order and connectivity within a list doesnt
matter..For ex:

Input:
------
A B C D E F
A 0 1 0 0 0 1
B 1 0 0 0 0 0
C 0 0 0 1 0 0
D 0 0 1 0 1 0
E 0 0 0 1 0 0
F 1 0 0 0 0 0

Distinct Pairs : (A,B),(A,F),(C,D),(D,E)

Hence the output shd be : (A,B,F)
------ (C,D,E) 2 lists

The matrix is essentially a symmetric square matrix in which diagonal
elements are irrelevant.So, only (((N^2)/2) - N) are only stored to
reduce memory.

I have thought of an algorithm doing this job in O(N^3) time and
O(N) in space. Can any suggest me an algorithm better than this
complexity. N is very large for me, so I cant afford O(N^3)..Please
help..

[Andy Twigg]

Why not just use time O(n^2) to construct the connected components of
the graph? This is what you appear to want from your output.

-Andy

[Karthik]

I just didnt get ur point really...I want to say that here in the
problem you are not given the pairs, You are only provided with the
square matrix from where you shd derive the lists...Do u want to say
that it is still possible in a O(N^2) time?? If so plz explain..

[Karthik]

Can u just describe or send a link to the algorithm which converts
matrix into graph in O(N^2) time.....

[Andy Twigg]

Doesn't the matrix represent the graph? It is just the adjacency matrix
of the graph..