fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. void convertToDirectedTree(vector<vector<int>>& adj, int root, vector<vector<int>>& directedAdj) {
  9.     int n = adj.size();
  10.     vector<bool> visited(n, false);
  11.     queue<int> q;
  12.  
  13.     q.push(root);
  14.     visited[root] = true;
  15.  
  16.     while (!q.empty()) {
  17.         int node = q.front();
  18.         q.pop();
  19.  
  20.         for (int neighbor : adj[node]) {
  21.             if (!visited[neighbor]) {
  22.                 directedAdj[node].push_back(neighbor);
  23.                 visited[neighbor] = true;
  24.                 q.push(neighbor);
  25.             }
  26.         }
  27.     }
  28. }
  29.  
  30. int main() {
  31.     int n, root;
  32.     cout << "Enter number of nodes: ";
  33.     cin >> n;
  34.     vector<vector<int>> adj(n), directedAdj(n);
  35.  
  36.     cout << "Enter edges (u v) for an undirected tree:\n";
  37.     for (int i = 0; i < n - 1; i++) {
  38.         int u, v;
  39.         cin >> u >> v;
  40.         adj[u].push_back(v);
  41.         adj[v].push_back(u);
  42.     }
  43.  
  44.     cout << "Enter root node: ";
  45.     cin >> root;
  46.  
  47.     convertToDirectedTree(adj, root, directedAdj);
  48.  
  49.     // Sorting edges by the first element before output
  50.     vector<pair<int, int>> edges;
  51.     for (int i = 0; i < n; i++) {
  52.         for (int v : directedAdj[i]) {
  53.             edges.emplace_back(i, v);
  54.         }
  55.     }
  56.  
  57.     sort(edges.begin(), edges.end());
  58.  
  59.     cout << "Directed Tree Edges:\n";
  60.     for (const auto& edge : edges) {
  61.         cout << edge.first << " -> " << edge.second << endl;
  62.     }
  63.  
  64.     return 0;
  65. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
1 0
2 4
3 4
4 1
4
stdout
copy 
Enter number of nodes: Enter edges (u v) for an undirected tree:
Enter root node: Directed Tree Edges:
1 -> 0
4 -> 1
4 -> 2
4 -> 3
https://ideone.com/BCPS1j
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!