SHARE
TWEET

Untitled

a guest May 19th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef pair <ll,ll> pi;
  7. typedef vector <ll> vi;
  8.  
  9. const ld PI =  3.1415926535897932384626433832795L;
  10. const ld eps=1e-9;
  11. const int mod = 1e9 + 7;
  12. const int inf = INT_MAX;
  13. const int N = 10500, M = 100500;
  14.  
  15.  
  16. #define F first
  17. #define S second
  18. #define PB push_back
  19. #define rs resize
  20.  
  21. ll n,m,k,a,b,i,j,x,sum;
  22. ll ans=0;
  23. ll l=0,r=1e18;
  24. bool f=1;
  25. int dd[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
  26.  
  27. vi son[N];
  28. vi dp(N);
  29.  
  30. ll fun(ll v){
  31.     if(son[v].empty()){
  32.         return 1;
  33.     }
  34.     if(dp[v]) return dp[v];
  35.  
  36.     for(auto e:son[v]){
  37.         dp[v] = max(dp[v],fun(e) + 1);
  38.     }
  39. }
  40.  
  41. int main()
  42. {
  43.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  44.     cout<<fixed<<setprecision(20);
  45.     /*freopen("longpath.in", "r", stdin);
  46.     freopen("longpath.out", "w", stdout);*/
  47.     cin>>n>>m;
  48.     for(int i=0;i<m;i++)
  49.     {
  50.         ll v,to;
  51.         cin>>v>>to;
  52.         son[v].PB(to);
  53.     }
  54.     for(int i=1;i<=n;i++)
  55.     {
  56.         if(!dp[i]) fun(i);
  57.     }
  58.     for(auto e:dp) cout<<e<<" ";
  59.     return 0;
  60. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top