fork download 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6. void solve(vector<vector<int>>&graph,vector<int>&dp,vector<int>&indegrees,vector<int>&outdegrees){
  7.     queue<int>q;
  8.     int n=graph.size();
  9.     for(int i=0;i<n;i++){
  10.         if(indegrees[i]==0){
  11.             q.push(i);
  12.         }
  13.     }
  14.  
  15.     while(!q.empty()){
  16.         int node=q.front();
  17.         q.pop();
  18.  
  19.         for(auto&child:graph[node]){
  20.             dp[child]=max(dp[child],dp[node]+1);
  21.             indegrees[child]--;
  22.             if(indegrees[child]==0) q.push(child);
  23.         }
  24.         outdegrees[node]=0;
  25.     }
  26.  
  27. }
  28.  
  29. int main(){
  30.     int n;
  31.     cin>>n;
  32.     vector<vector<int>>graph(n);
  33.     vector<vector<int>>rev_graph(n);
  34.     int m;
  35.     cin>>m;
  36.     int i=0;
  37.     vector<int>indegrees(n,0);
  38.     vector<int>outdegrees(n,0);
  39.     vector<int>ins(n,0);
  40.     vector<int>outs(n,0);
  41.  
  42.     while(i<m){
  43.         int x,y;
  44.         cin>>x>>y;
  45.         graph[x].push_back(y);
  46.         rev_graph[y].push_back(x);
  47.         outdegrees[x]++;
  48.         indegrees[y]++;
  49.         ins[x]++;
  50.         outs[y]++;
  51.         i++;
  52.     }
  53.  
  54.     vector<int>dp(n,0);
  55.     vector<int>rev_dp(n,0);
  56.  
  57.     solve(graph,dp,indegrees,outdegrees);
  58.     solve(rev_graph,rev_dp,ins,outs);
  59.  
  60.     for(int i=0;i<n;i++){
  61.         cout<<"Node: "<<i<<": longest path including this node: "<<dp[i]+rev_dp[i]+1<<endl;
  62.     }
  63.  
  64.     return 0;
  65. }
Success #stdin #stdout 0s 5328KB
comments (?)
stdin 
5 5 
0 1
0 2
1 3
2 3
3 4
stdout 
Node: 0: longest path including this node: 4
Node: 1: longest path including this node: 4
Node: 2: longest path including this node: 4
Node: 3: longest path including this node: 4
Node: 4: longest path including this node: 4
https://ideone.com/I5PU81
language:
C++ (gcc 8.3)
created:
10 hours 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!