2471. From adjacency matrix to the list of edges

A simple undirected graph is given by adjacency matrix. Print its representation as a list of edges.

Input. The first line contains the number  of vertices n (1 ≤ n ≤ 100) in the graph. The next n lines contain the adjacency matrix of the graph.

Output. Print the list of edges of the graph, ordered by the first vertex in each pair.

Sample input	Sample output
3 0 1 1 1 0 1 1 1 0	1 2 1 3 2 3

SOLUTION

graphs

Algorithm analysis

We’ll print the list of edges “on the fly” by processing the adjacency matrix sequentially: row by row from top to bottom, and within each row from left to right. For each entry equal to 1 in the adjacency matrix, print the pair of vertices that defines the corresponding edge. With this traversal, the vertex pairs are automatically ordered by the first vertex.

Example

The graph shown in the example has the following form:

Algorithm implementation

Read the adjacency matrix of the graph. Since the graph is undirected, print only those edges (i, j) for which i < j.

scanf("%d",&n);

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

{

scanf("%d",&val);

if (i < j && val == 1)

printf("%d %d\n",i,j);

}

Java implementation

import java.util.*;

import java.io.*;

public class Main

{

public static void main(String[] args) throws IOException

{

//Scanner con = new Scanner(new FileReader ("2471.in"));

Scanner con = new Scanner(System.in);

int n = con.nextInt();

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

{

int val = con.nextInt();

if (i < j && val == 1)

System.out.println(i + " " + j);

}

con.close();

}

}