Advertisement
Guest User

Untitled

a guest
Jan 28th, 2020
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. //#include "optimization.h"
  6.  
  7. using namespace std;
  8.  
  9. vector<int> used;
  10.  
  11. void dfs(int v, vector<vector<int> > &g) {
  12.     for (int u : g[v]) {
  13.         if (!used[u]) {
  14.             dfs(u, g);
  15.         }
  16.         used[v] = max(used[v], used[u]);
  17.     }
  18.     ++used[v];
  19. }
  20.  
  21. int main() {
  22.     ios_base::sync_with_stdio(0);
  23.     cin.tie(0);
  24.     cout.tie(0);
  25.    
  26.     int n, m;
  27.     cin >> n >> m;
  28.     vector<vector<int> > v(n);
  29.     for (int i = 0; i < m; ++i) {
  30.         int a, b;
  31.         cin >> a >> b;
  32.         --a;
  33.         --b;
  34.         v[a].push_back(b);
  35.     }
  36.     used.resize(n);
  37.     for (int i = 0; i < n; ++i) {
  38.         if (!used[i]) {
  39.             dfs(i, v);
  40.         }
  41.     }
  42.     cout << *max_element(used.begin(), used.end()) - 1;
  43. }
  44.  
  45. /*
  46. 5 5
  47.  1 2
  48.  2 3
  49.  3 4
  50.  3 5
  51.  1 5
  52.  */
  53.  
  54. /*
  55.  4 2 1 1 4 2
  56.  ..*.
  57.  *...
  58.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement