fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> countReverseEdges(int g_nodes, vector<int> g_from, vector<int> g_to) {
  5.     int n = g_nodes;
  6.     vector<vector<int>> adj(n);
  7.     set<pair<int, int>> dir_edges;
  8.  
  9.     for (int i = 0; i < g_from.size(); ++i) {
  10.         int u = g_from[i] - 1;
  11.         int v = g_to[i] - 1;
  12.         adj[u].push_back(v);
  13.         adj[v].push_back(u);
  14.         dir_edges.insert({u, v});
  15.     }
  16.  
  17.     vector<int> ans(n, 0);
  18.     int cost_root_0 = 0;
  19.  
  20.     function<void(int, int)> dfs1 = [&](int u, int p) {
  21.         for (int v : adj[u]) {
  22.             if (v == p) continue;
  23.             if (dir_edges.count({v, u})) {
  24.                 cost_root_0++;
  25.             }
  26.             dfs1(v, u);
  27.         }
  28.     };
  29.  
  30.     dfs1(0, -1);
  31.     ans[0] = cost_root_0;
  32.  
  33.     function<void(int, int)> dfs2 = [&](int u, int p) {
  34.         for (int v : adj[u]) {
  35.             if (v == p) continue;
  36.             if (dir_edges.count({u, v})) {
  37.                 ans[v] = ans[u] + 1;
  38.             } else {
  39.                 ans[v] = ans[u] - 1;
  40.             }
  41.             dfs2(v, u);
  42.         }
  43.     };
  44.  
  45.     dfs2(0, -1);
  46.  
  47.     return ans;
  48. }
  49.  
  50. int main() {
  51.     ios::sync_with_stdio(false);
  52.     cin.tie(nullptr);
  53.  
  54.     int n, m;
  55.     cin >> n >> m;
  56.     vector<int> from(m), to(m);
  57.     for (int i = 0; i < m; ++i) {
  58.         cin >> from[i] >> to[i];
  59.     }
  60.  
  61.     vector<int> result = countReverseEdges(n, from, to);
  62.  
  63.     for (int x : result)
  64.         cout << x << " ";
  65.     cout << "\n";
  66.  
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
3 2
2 2 1 3
stdout 
0 0 1
https://ideone.com/4YhfXr
language:
C++ (gcc 8.3)
created:
3 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!