3981 . From adjacency matrix to adjacency list

A simple undirected graph is given with an adjacency matrix. Print its representation in the form of adjacency list.

Input. The first line contains the number of vertices in a graph n (1 ≤ n ≤ 100). Then the adjacency matrix is given. It is guaranteed that a graph does not contain loops.

Output.  Print n lines – the adjacency lists of the graph. Print in the i-th line the number of edges adjacent to the i-th vertex, and then the vertex numbers where these edges go in increasing order.

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

SOLUTION

graphs

Algorithm analysis

Read the adjacency matrix, construct and print an adjacency list.

Example

Sample graph has the next form.

Algorithm realization

Declare an adjacency list of the graph.

vector<vector<int> > g;

Read the input data. Vertices are numbered from 1 to n. Construct an adjacency list of the graph.

scanf("%d", &n);

g.resize(n + 1);

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

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

{

scanf("%d", &val);

if (val) g[i].push_back(j);

}

Print an adjacency list.

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

{

printf("%d", g[i].size());

for (j = 0; j < g[i].size(); j++)

printf(" %d", g[i][j]);

printf("\n");

}

Java realization – array of ArrayList

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

ArrayList<Integer>[] g = new ArrayList[n+1]; // unchecked

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

g[i] = new ArrayList<Integer>();

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

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

{

int val = con.nextInt();

if (val == 1) g[i].add(j);

}

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

{

System.out.print(g[i].size());

for(int j = 0; j < g[i].size(); j++)

System.out.print(" " + g[i].get(j));

System.out.println();

}

con.close();

}

}

Java realization – ArrayList of ArrayList

import java.util.*;

import java.io.*;

public class Main

{

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

{

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

Scanner con = new Scanner(System.in);

int n = con.nextInt();

ArrayList<ArrayList<Integer>> g =

new ArrayList<ArrayList<Integer>>();

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

g.add(new ArrayList<Integer>());

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

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

{

int val = con.nextInt();

if (val == 1) g.get(i).add(j);

}

//System.out.println(g);

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

{

System.out.print(g.get(i).size());

for(int j = 0; j < g.get(i).size(); j++)

System.out.print(" " + g.get(i).get(j));

System.out.println();

}

con.close();

}

}