/////////************** GRAPHS IN C++ **********////////////////

/// graphs are combination of nodes and edges 
// nodes = entity in which data is stored
// edges = connecting line which connect the nodes 
// degree = no of edges connected



////// types of graphs

// undirected graph = arrow will not be provided ... (v---u == u--v)

// directed graph = arrow will  be provided ... (v---u != u--v)

// they're two type of degree in directed 
// indegree = edges coming inside  my way  
// outdegree = edges coming out of  way  

// wieghted graph = theyre are wieghted writeen on edges(like numbers) default wieght is 1 

/// path = squence of nodes reaching (nodes written will not repeat)

// cyclic graph = when we create a path in which we reach the node which we written in previous order also. (like a-b-c-d and we d-a this cyclic graph)

/// TYPES OF REPRESENATATION 

/// i) adjacency matrix 
///  in this 2d matrix is made....
/// space complexity = O(n^2)

/// ii) adjacency list 
// in this we write the node connected with one and another in the form of list.



#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;

class graph {
public:
    unordered_map<int, list<int>> adj; // here we mapping a number with another number 

    void addEdge(int u, int v, bool direction) { // u and v are edges and bool for undirected and directed graph 
        // direction = 0 -> undirected graph
        // direction = 1 -> directed graph

        // creating an edge from u to v 
        adj[u].push_back(v); // created 
        if (direction == 0) { // checking directed or undirected 
            adj[v].push_back(u); // corrected from push.back to push_back
        }
    }

    void printAdjList() { // Removed the duplicate declaration
        for (auto i : adj) {
            cout << i.first << " -> ";
            for (auto j : i.second) {
                cout << j << ", ";
            }
            cout << endl; // Move to the next line after printing the list for a node
        }
    }
};

int main() {
    int n;
    cout << "Enter the number of nodes: " << endl;
    cin >> n;

    int m;
    cout << "Enter the number of edges: " << endl;
    cin >> m;

    graph g;

    for (int i = 0; i < m; i++) {
        int u, v;
        cout << "Enter edge (u v): "; // Prompt for edge input
        cin >> u >> v;

        // Ask the user for the type of graph
        int direction;
        cout << "Is the graph directed (1) or undirected (0)? ";
        cin >> direction;

        // creation of graph based on user input
        g.addEdge(u, v, direction);
    }

    // printing graph 
    g.printAdjList();

    return 0;
}