fork(1) download
copy 
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8.  
  9. vector<vector<int> > g;
  10. vector<int> time_in,time_out,hieght;
  11. int n,timee,flag;
  12. void make_graph()
  13. {
  14.     g.clear();
  15.     g.resize(n);
  16.     time_in.clear();
  17.     time_in.resize(n+1,-1);
  18.     time_out.clear();
  19.     time_out.resize(n+1,-1);
  20.     hieght.clear();
  21.     hieght.resize(n+1,0);
  22.     timee=0;
  23.     flag=0;
  24.     int i,r,u,v;
  25.     cin>>r;
  26.     for(i=1;i<=r;i++)
  27.     {
  28.         cin>>u>>v;
  29.         g[u].push_back(v);
  30.     }
  31. }
  32.  
  33.  
  34. int topological_Sort_Util(int v, stack<int> &Stack)
  35. {
  36.     int i,ans=0;
  37.     time_in[v]=++timee;
  38.     for (i = 0; i < g[v].size(); ++i)
  39.         {
  40.             int curr;
  41.             if (time_in[g[v][i]]<0)
  42.             {
  43.                 curr=topological_Sort_Util(g[v][i], Stack);
  44.             }
  45.             else
  46.             {
  47.                 if(time_out[g[v][i]]>0)
  48.                 {
  49.                     curr=hieght[g[v][i]];
  50.                 }
  51.                 else
  52.                 {
  53.                     flag=-1;
  54.                     break;
  55.                 }
  56.             }
  57.              if(ans<curr)ans=curr;
  58.         }
  59.         if(flag==-1)
  60.             return -1;
  61.         ans++;
  62.         time_out[v]=++timee;
  63.         hieght[v]=ans;
  64.     // Push current vertex to stack which stores result
  65.     Stack.push(v);
  66.     return ans;
  67. }
  68.  
  69. void topological_Sort()
  70. {
  71.     stack<int> Stack;
  72.  
  73.     for (int i = 0; i < n; i++)
  74.       if (time_in[i] < 0)
  75.         topological_Sort_Util(i, Stack);
  76.  
  77.     while (Stack.empty() == false && flag!=-1)
  78.     {
  79.         //cout << Stack.top() << " ";
  80.         Stack.pop();
  81.     }
  82. }
  83. int main()
  84. {
  85.     int t,x;
  86.     cin>>t;
  87.     for(x=1;x<=t;x++)
  88.     {
  89.         cin>>n;
  90.         make_graph();
  91.         topological_Sort();
  92.         int i,ans=0;
  93.         for(i=0;i<n;i++)
  94.             if(hieght[i]>ans)ans=hieght[i];
  95.  
  96.         if(flag==-1)
  97.         {
  98.             cout<<"Case "<<x<<": Never Ends\n";
  99.         }
  100.         else
  101.         {
  102.             cout<<"Case "<<x<<": "<<ans<<" semester(s)\n";
  103.         }
  104.     }
  105.     return 0;
  106. }
  107.  
Runtime error #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oVTst6
language:
C++ (gcc 8.3)
created:
10 years 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!