fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. pair<bool,int> Topo(vector<vector<int>> &adj) {
  6.     int n = adj.size();
  7.     vector<int> indegree(n, 0);
  8.  
  9.     for (int i = 0; i < n; i++) {
  10.         for (auto j : adj[i]) {
  11.             indegree[j]++;
  12.         }
  13.     }
  14.  
  15.     queue<int> q;
  16.     for (int i = 0; i < n; i++) {
  17.         if (indegree[i] == 0) {
  18.             q.push(i);
  19.         }
  20.     }
  21.  
  22.     vector<int> topo_sort;
  23.     int semesters = 0;
  24.  
  25.     while (!q.empty()) {
  26.         int levelSize = q.size();
  27.         semesters++;
  28.  
  29.         for (int i = 0; i < levelSize; i++) {
  30.             int node = q.front(); q.pop();
  31.             topo_sort.push_back(node);
  32.  
  33.             for (int neighbor : adj[node]) {
  34.                 indegree[neighbor]--;
  35.                 if (indegree[neighbor] == 0) {
  36.                     q.push(neighbor);
  37.                 }
  38.             }
  39.         }
  40.     }
  41.  
  42.     bool hasCycle = (topo_sort.size() != n);
  43.     return { !hasCycle, semesters };
  44. }
  45.  
  46. void solve() {
  47.     int n, e;
  48.     cin >> n >> e;
  49.     vector<vector<int>> adj(n+1);
  50.  
  51.     for (int i = 0; i < e; i++) {
  52.         int from, to;
  53.         cin >> from >> to;
  54.         adj[from].push_back(to);
  55.     }
  56.  
  57.     auto [isValid, semesters] = Topo(adj);
  58.  
  59.     if (!isValid) {
  60.         cout << -1 << "\n";
  61.         return;
  62.     }
  63.  
  64.     cout << semesters << "\n";
  65. }
  66.  
  67. int main() {
  68.     solve();
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3  2
1 3
2 3
stdout
copy 
2
https://ideone.com/IbbiAS
language:
C++ (gcc 8.3)
created:
1 day 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!