Read the edges of an undirected graph and list the neighbours of every vertex in order.
What to build
An adjacency matrix, and a report made by reading its rows.
Requirements
- Store each edge in both directions.
- Print one line for each vertex: its number, a colon, and its neighbours in increasing order.
- Print
-for a vertex with no neighbours.
Input
The first line has n and m. Each of the next m lines has an edge u v. No edge is repeated, and no edge joins a vertex to itself.
Output
n lines, such as 0: 1 2 or 3: -.
Constraints
1 ≤ n ≤ 50 and 0 ≤ m ≤ 1000.
Example
Input:
4 3
0 1
0 2
2 3
Output:
0: 1 2
1: 0
2: 0 3
3: 2
Why it works
Row u of an adjacency matrix has a 1 in column v exactly when the two are joined. Scanning the row from left to right meets the neighbours in increasing order, with no sorting.
Examples
Example 1 · Input
4 3 0 1 0 2 2 3
Expected output
0: 1 2 1: 0 2: 0 3 3: 2
Example 2 · Input
2 0
Expected output
0: - 1: -
Hints
Hint 1
Store the graph in an adjacency matrix, setting both adj[u][v] and adj[v][u].
Hint 2
Row u of the matrix, read from left to right, gives the neighbours of u in increasing order.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int adj[50][50];
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u][v] = 1;
adj[v][u] = 1;
}
for (int u = 0; u < n; u++) {
int any = 0;
printf("%d:", u);
for (int v = 0; v < n; v++) {
if (adj[u][v]) {
printf(" %d", v);
any = 1;
}
}
if (!any) printf(" -");
printf("\n");
}
return 0;
}