グラフのエッジカラーリングを実行するC++プログラム

このプログラムでは、グラフのエッジの彩色を実行します。この場合、隣接する2つのエッジが同じ色にならないように、グラフのエッジに彩色する必要があります。例の手順

アルゴリズム

Begin
   Take the input of the number of vertices, n, and then number of edges, e, in the graph.
   The graph is stored as adjacency list.
   BFS is implemented using queue and colors are assigned to each edge.
End

例

#include<bits/stdc++.h>
using namespace std;
int n, e, i, j;
vector<vector<pair<int, int> > > g;
vector<int> color;
bool v[111001];
void col(int n) {
   queue<int> q;
   int c = 0;
   set<int> vertex_colored;
   if(v[n])
      return;
      v[n] = 1;
   for(i = 0;i<g[n].size();i++) {
      if(color[g[n][i].second]!=-1) {
         vertex_colored.insert(color[g[n][i].second]);
      }
   }
   for(i = 0;i<g[n].size();i++) {
      if(!v[g[n][i].first]) {
         q.push(g[n][i].first);
      }
      if(color[g[n][i].second]==-1) {
         while(vertex_colored.find(c)!=vertex_colored.end())
            c++;
            color[g[n][i].second] = c;
            vertex_colored.insert(c);
            c++;
      }
   }
   while(!q.empty()) {
      int temp = q.front();
      q.pop();
      col(temp);
   }
   return;
}
int main() {
   int u,w;
   set<int> empty;
   cout<<"Enter number of vertices and edges respectively:";
   cin>>n>>e;
   cout<<"\n";
   g.resize(n); //number of vertices
   color.resize(e,-1); //number of edges
   memset(v,0,sizeof(v));
   for(i = 0;i<e;i++) {
      cout<<"\nEnter edge vertices of edge "<<i+1<<" :"<<"\n";
      cin>>u>>w;
      u--; w--;
      g[u].push_back(make_pair(w,i));
      g[w].push_back(make_pair(u,i));
   }
   col(0);
   for(i = 0;i<e;i++) {
      cout<<"Edge "<<i+1<<" is coloured with colour "<<color[i]+1
      << "\n";
   }
}

出力

Enter number of vertices and edges respectively:4 5
Enter edge vertices of edge 1 :1 2
Enter edge vertices of edge 2 :2 3
Enter edge vertices of edge 3 :1 1
Enter edge vertices of edge 4 :3 4
Enter edge vertices of edge 5 :1 4
Edge 1 is coloured with colour 1
Edge 2 is coloured with colour 2
Edge 3 is coloured with colour 2
Edge 4 is coloured with colour 1
Edge 5 is coloured with colour 3