그래프의 가장자리 색칠을 수행하는 C++ 프로그램

이 프로그램에서 우리는 두 개의 인접한 가장자리가 같은 색을 가지지 않도록 그래프의 가장자리를 색칠해야 하는 그래프의 가장자리 색칠을 수행할 것입니다. 예제의 단계.

알고리즘

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