C++에서 길이가 1보다 큰 경로가 없도록 무방향 그래프를 방향 그래프로 변환

이 튜토리얼에서는 길이가 1보다 큰 경로가 없도록 무방향 그래프를 방향 그래프로 변환하는 프로그램에 대해 설명합니다.

이를 위해 무방향 그래프가 제공됩니다. 우리의 임무는 길이가 1보다 큰 경로가 없는 경우 해당 그래프를 직접 그래프로 변환하는 것입니다.

예시

#include <bits/stdc++.h>
using namespace std;
#define N 100005
//storing the graph
vector<int> gr[N];
//storing colour of each vertex
int colour[N];
vector<pair<int, int> > edges;
bool bip;
//adding edges to the graph
void add_edge(int x, int y){
   gr[x].push_back(y);
   gr[y].push_back(x);
   edges.push_back(make_pair(x, y));
}
//checking if the given graph
//is bipartite
void dfs(int x, int col){
   colour[x] = col;
   //moving to the child vertices
   for (auto i : gr[x]) {
      if (colour[i] == -1)
         dfs(i, col ^ 1);
      //if child and parent having
      //same branch
      else if (colour[i] == col)
         bip = false;
   }
}
//converting into direct graph
void convert_directed(int n, int m){
   memset(colour, -1, sizeof colour);
   bip = true;
   //calling bipartite function
   dfs(1, 1);
   if (!bip) {
      cout << -1;
      return;
   }
   //if bipartite is possible
   for (int i = 0; i < m; i++) {
      if (colour[edges[i].first] == 0)
         swap(edges[i].first, edges[i].second);
      cout << edges[i].first << " " << edges[i].second << endl;
   }
}
int main(){
   int n = 4, m = 3;
   add_edge(1, 2);
   add_edge(1, 3);
   add_edge(1, 4);
   convert_directed(n, m);
   return 0;
}

출력

1 2
1 3
1 4