fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. void makegraph(vector<vector<ll>> &graph, vector<vector<ll>> &adj) {
  5.     vector<bool> vis(graph.size() + 1, false);
  6.     queue<ll> q;
  7.     q.push(1);
  8.     vis[1] = true;
  9.     while (!q.empty()) {
  10.         ll node = q.front();
  11.         q.pop();
  12.         for (auto it : adj[node]) {
  13.             if (it != node) {
  14.                 graph[node].push_back(it);
  15.                 // cout << node << " " << it << " \n";
  16.                 q.push(it);
  17.             }
  18.         }
  19.     }
  20.  
  21.  
  22. }
  23.  
  24.  
  25.  
  26.  
  27. bool can(const vector<vector<ll>> &adj, ll n) {
  28.     queue<ll> q;
  29.     q.push(1);
  30.     vector<bool> vis(n + 1, false);
  31.     vis[1] = true;
  32.  
  33.     while (!q.empty()) {
  34.         ll node = q.front();
  35.         q.pop();
  36.         for (auto it : adj[node]) {
  37.             if (!vis[it]) {
  38.                 q.push(it);
  39.                 vis[it] = true;
  40.             }
  41.         }
  42.     }
  43.  
  44.     return !vis[n];
  45. }
  46.  
  47. int main() {
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(NULL);
  50. #ifndef ONLINE_JUDGE
  51.     freopen("input.txt" , "r" , stdin);
  52.     freopen("output.txt" , "w" , stdout);
  53. #endif
  54.     ll n, m;
  55.     cin >> n >> m;
  56.     vector<vector<ll>> adj(n + 1);
  57.     while (m--) {
  58.         ll u, v;
  59.         cin >> u >> v;
  60.         adj[u].push_back(v);
  61.     }
  62.  
  63.     if (can(adj, n)) {
  64.         cout << -1 << '\n';
  65.         return 0;
  66.     }
  67.  
  68.     queue<ll> q;
  69.  
  70.     vector<vector<ll>> graph(n + 1);
  71.  
  72.     vector<ll> indegree(n + 1, 0);
  73.     vector<bool> vis(n + 1, false);
  74.     vector<ll> dis(n + 1, INT_MIN);
  75.     makegraph(graph,  adj);
  76.     for (auto it : graph) {
  77.         for (auto k : it) {
  78.             indegree[k]++;
  79.         }
  80.     }
  81.     q.push(1);
  82.     vis[1] = true;
  83.     dis[1] = 1;
  84.  
  85.     while (!q.empty()) {
  86.         ll node = q.front();
  87.         q.pop();
  88.         for (auto it : graph[node]) {
  89.             if (!vis[it]) {
  90.                 indegree[it]--;
  91.                 if (indegree[it] == 0) {
  92.                     q.push(it);
  93.                     dis[it] = max(dis[it], dis[node] + 1);
  94.                 }
  95.             }
  96.         }
  97.     }
  98.  
  99.     cout << dis[n] << '\n';
  100.  
  101.  
  102.     return 0;
  103. }
  104.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
10 10
2 6
1 2
4 6
5 6
2 5
7 8
6 10
1 10
3 5
4 9
stdout
copy 
5
https://ideone.com/BQ0rBq
language:
C++14 (gcc 8.3)
created:
11 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!