You are given an undirected graph of 'N' nodes and 'M' edges. Your task is to create the graph and print the adjacency list of the graph. It is guaranteed that all the edges are unique, i.e., if there is an edge from 'X' to 'Y', then there is no edge present from 'Y' to 'X' and vice versa. Also, there are no self-loops present in the graph.
In graph theory, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.
If 'N' = 3 and edges = {{2,1}, {2,0}}.
So, the adjacency list of the graph is stated below.
0 → 2
1 → 2
2 → 0 → 1
The first line contains two space-separated integers 'N' and 'M', denoting the total number of nodes and the number of edges, respectively.
Then 'M' lines follow. Each line contains two space-separated integers denoting the nodes that are connected by the current edge.
It is guaranteed that all the edges are unique and there are no self-loops present in the graph.
Print the adjacency list of the graph. Total 'N' lines will be printed where 'N' is the number of nodes.
In each line, the first integer denotes the number of the node, and then the neighbors to this node are printed separated by a single space in ascending order.
You can return any valid adjacency representation of the graph.
You do not need to print anything. It has already been taken care of. Just implement the given function.
4 3
1 2
0 3
2 3
0 3
1 2
2 1 3
3 0 2
The graph is shown in the below figure.
So, the neighbour of node 0 is 3. So, in the first line, the first integer is 0 followed by its neighbour 3. Similarly in the second line, 1 is followed by its neighbour 2.
In the third line, 2 is followed by its neighbours 1 and 3. And in the fourth line, 3 is followed by its neighbours 0 and 2.
3 3
0 1
1 2
2 0
0 1 2
1 0 2
2 0 1
The graph is shown in the below figure.
So, the neighbour of node 0 is 1 and 2. So, in the first line, the first integer is 0 followed by its neighbour 1 and 2. Similarly in the second line, 1 is followed by its neighbour 2 and 0.
In the third line, 2 is followed by its neighbours 1 and 0.
1 <= N <= 5000
1 <= M <= min(5000, (N * (N - 1)) / 2)
0 <= edges[i][0], edges[i][1] <= N-1
Time limit: 1 sec
Try to store the graph in an array of N nodes and print all its neighbours.
Algorithm:
O(N + M), where N and M denote the number of nodes and the number of edges in the graph, respectively.
We are traversing each node and each edge of the graph, so the overall time complexity is O(N + M).
O(N + M), where N and M denote the number of nodes and the number of edges in the graph, respectively.
The graph array and the adjacencyList array both contain a total of N nodes and M edge. So, the overall space complexity is O(N + M).
All tags
Sort by
Interview problems
c++
#include<bits/stdc++.h>
using namespace std;
void addEdge(int u, int v, vector< vector<int>> &adj){
adj[u].push_back(v);
adj[v].push_back(u);
}
vector < vector < int >> printAdjacency(int n, int m, vector < vector < int >> & edges) {
vector< vector<int>> adj(n);
for(int i=0; i<n; i++){
adj[i].push_back(i);
}
for(int i=0; i<m; i++){
addEdge(edges[i][0], edges[i][1], adj);
}
return adj;
} Interview problems
C++
vector < vector < int >> printAdjacency(int n, int m, vector < vector < int >> & edges) {
vector<vector<int>> adj(n);
for(auto x: edges) {
int u=x[0], v=x[1];
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=0;i<n;i++) {
sort(adj[i].begin(), adj[i].end());
adj[i].insert(adj[i].begin(), i);
}
return adj;
}Interview problems
Easy Solution
vector < vector < int >> printAdjacency(int n, int m, vector < vector < int >> & edges) {
// Write your code here.
vector < vector < int >>adjList(n);
for(int i = 0;i<n;i++){
adjList[i].push_back(i);
}
for(int i = 0;i<m;i++){
int u = edges[i][0];
int v = edges[i][1];
adjList[u].push_back(v);
adjList[v].push_back(u);
}
return adjList;
}Interview problems
cpp soln
vector < vector < int >> printAdjacency(int n, int m, vector < vector < int >> & edges) {
vector<int>adj[n];
for(int i = 0; i < m; i++)
{
int u = edges[i][0];
int v = edges[i][1];
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<vector<int>>ans;
for(int i = 0; i < n; i++)
{
vector<int>temp;
temp.push_back(i);
for(auto x : adj[i])
{
temp.push_back(x);
}
ans.push_back(temp);
}
return ans;
}Interview problems
c++ easy solution
vector < vector < int >> printAdjacency(int n, int m, vector < vector < int >> & edges) {
vector<int> ans[n];
//ans array will store all the adjacent nodes corresponding on index
for(int i=0; i<m; i++){
int u = edges[i][0];
int v = edges[i][1];
ans[u].push_back(v);
ans[v].push_back(u);
}
vector<vector<int> > adj(n);
//entering neighbours
for(int i=0; i<n; i++){
adj[i].push_back(i);
for(int j=0; j<ans[i].size(); j++){
adj[i].push_back(ans[i][j]);
}
}
return adj;
}c
Interview problems
Solution
vector<vector<int>> printAdjacency(int n, int m, vector<vector<int>>& edges) {
vector<vector<int>> ans(n);
for (int i = 0; i < n; i++) {
ans[i].push_back(i);
}
for (int i = 0; i < m; i++) {
int u = edges[i][0];
int v = edges[i][1];
ans[u].push_back(v);
ans[v].push_back(u);
}
return ans;
}
Interview problems
Easiest Solution Explained in Hindi
vector<vector<int>> printAdjacency(int n, int m, vector<vector<int>> &edges)
{
// Adjacency Matrix Create hoggya
vector<vector<int>> adj(n);
for(int j = 0 ; j < n ; j++)// Idhr hmlog sbko khudse conect kr rahe hai matlab manle 1st node sbse pelhe khudse connect hoga tbna aage jaayga wahi wahi hmlog self node add kr rahe hai
{
adj[j].push_back(j);
}
// Idhr dekh isme hmlog do values aara input me usko dekhre u hogya pelha value v hogya dusra value dono ka number me matric me hmlog connection banare hai u ka v ke saath v ka u ke saath
for (int i = 0; i < m; i++)
{
int u = edges[i][0];
int v = edges[i][1];
// Assuming the graph is undirected, add edges in both directions
adj[u].push_back(v);
adj[v].push_back(u);
}
return adj;
}
Interview problems
Commented C++ Soln
//Basically, we gotta print Adj 2d vec of size n (no of nodes)
//starting from 0 to n-1
//Each index/nodes will have a vec of its adjacent nodes
vector < vector < int >> printAdjacency(int n, int m, vector < vector < int >> & edges) {
vector<vector<int>> adj(n);
for(int i=0; i<n; i++){
adj[i].push_back(i);
}
//basically intitalising the adj 2 vec
// {
// {0,0},
// {1,1},
// . till n times.
// }
// So we can access it later using indexing.
//edges is like this: for nodes=4 and m-edges=3
// 1 2
// 0 3
// 2 3
for(int i=0; i<m; i++){
int u = edges[i][0];
int v = edges[i][1];
adj[u].push_back(v);
adj[v].push_back(u);
}
return adj;
}
Interview problems
easiest self explanatory : feels motivated
vector < vector < int >> printAdjacency(int n, int m, vector < vector < int >> & edges) {
vector<vector<int>>ans(n);
for(int i=0;i<n;i++){
ans[i].push_back(i);
}
for(auto &edge:edges){
int u = edge[0];
int v = edge[1];
ans[u].push_back(v); // Add v to the adjacency list of u
ans[v].push_back(u); // Assuming undirected graph, add u to the adjacency list of v as well
}
return ans;
}
Interview problems
Java Most Easiest Solution Using Adjacency List
import java.util.ArrayList;
public class Solution {
public static int[][] printAdjacency(int n, int m, int[][] edges) {
// Write your code here.
ArrayList<Integer>[] adjList = new ArrayList[n];
// create graph for the n vertex
for(int i = 0; i < n; i++){
adjList[i] = new ArrayList<>();
}
// connect vertex with edges
for(int i = 0; i < m; i++){
int u = edges[i][0];
int v = edges[i][1];
adjList[u].add(v);
adjList[v].add(u);
}
// prepare output matrix
int[][] mat = new int[n][];
for(int i = 0; i < n; i++){
// add row number to the head of the list
adjList[i].add(0,i);
int k = adjList[i].size();
// initialized array for each list of rows
mat[i] = new int[k];
// intialize values in the corresponding row&col coordinate
for(int j = 0;j < k; j++){
mat[i][j] = adjList[i].get(j);
}
}
return mat;
}
}
