Advertisement
Mirbek

Максимум по минимуму

Jan 9th, 2022
1,196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5 + 3;
  6.  
  7. int n, m;
  8. int used[N], dist[N], par[N];
  9. vector <int> g[N];
  10.  
  11. int main(){
  12.     cin >> n >> m;
  13.  
  14.     int start;
  15.     cin >> start;
  16.  
  17.     for (int i = 1; i <= m; i++) {
  18.         int a, b;
  19.         cin >> a >> b;
  20.         g[b].push_back(a);
  21.     }
  22.  
  23.     for (int i = 1; i <= n; i++) {
  24.         dist[i] = -1;
  25.     }
  26.  
  27.     queue <int> q;
  28.     dist[start] = 0;
  29.     used[start] = 1;
  30.     q.push(start);
  31.  
  32.     while (!q.empty()) {
  33.         int v = q.front();
  34.         q.pop();
  35.         for (int i = 0; i < g[v].size(); i++) {
  36.             int to = g[v][i];
  37.             if (!used[to]) {
  38.                 used[to] = 1;
  39.                 dist[to] = dist[v] + 1;
  40.                 q.push(to);
  41.             }
  42.         }
  43.     }
  44.  
  45.     int mx = 0;
  46.     for (int i = 1; i <= n; i++) {
  47.         mx = max(mx, dist[i]);
  48.     }
  49.  
  50.     cout << mx << endl;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement