โปรแกรม C++ ทำ Edge Coloring ของกราฟ

ในโปรแกรมนี้จะทำ Edge Coloring ของกราฟ ซึ่งต้องระบายสีขอบของกราฟโดยที่ขอบที่อยู่ติดกันไม่มีสีเหมือนกัน

อัลกอริทึม

Begin
  รับจำนวนโหนด n และจำนวนขอบ e
  กราฟเก็บเป็น adjacency list
  BFS ใช้ queue และกำหนดสีให้แต่ละขอบ
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);
  color.resize(e, -1);
  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