c++graphundirected-graph

Create a graph if nodes are not continuous c++


Consider this situation: (undirected graph) we dont have number of nodes but have the edges like 1<->3 , 6<->7, 3<->7. So how do we declare a graph using this?

Generally we have n that is no. of node and e edges but in this case we only have e edges and that too not continuous i.e. instead of 1,2,3,4(or zero indexed) we have 1,3,6,7. I know we should use a map to convert these 1,3,6,7 values to 1,2,3,4 but how?

how we generally declare a graph

vector<int> adj[100000];
for(int i=0;i<e;i++)
{
  int u,v;
  cin>>u>>v;
  //need some mapping technique here to make this continuous
  adj[u].push_back(v);
  adj[v].push_back(u);
}

//iterate according to situation

Solution

  • I tried few combinations and this approach works well e-> no. of edges

    this approach maps the input vertices to respective values in map from 0 based index. Helpful to apply various algorithms directly without worrying about the input as much.

    int i=0;
    while(e>=0)
        {
            e--;
            int a1,a2;
            cin>>a1>>a2;
            //a1
            if(mp.find(a1)!=mp.end())
                a1 = mp[a1];
            else
            {
                
                mp[a1] = i;
                a1 = i;
                i++; 
            } 
            //a2  
            if(mp.find(a2)!=mp.end())
                a2 = mp[a2];
            else
            {
                
                mp[a2] = i;
                a2 = i;
                i++; 
            } 
            adj[a1].push_back(a2);
            adj[a2].push_back(a1);
        }