VasilM

Максимален път

May 21st, 2014
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include <iostream>
  2. #define MAXN 1000
  3.  
  4. using namespace std;
  5.  
  6.  
  7. int U[MAXN+1], S[MAXN], P[MAXN], G[MAXN][MAXN];
  8. int maxPath // = 0, currentPath = 0;
  9. int N,M;
  10.  
  11. void DFS_R(int r)
  12. {  
  13.    int y;
  14.    while(G[r][0]>0)
  15.    {
  16.     y=G[r][G[r][0]--];
  17.     if(!U[y]) { U[y]=1; P[y]=r; DFS_R(y); }
  18.    }
  19.    maxPath++;
  20.  
  21. // if( currentPath > maxPath ){
  22. //  maxPath = currentPath;
  23. // }
  24. // currentPath++;
  25. }
  26.  
  27. void first_call()
  28. {
  29.   for(int i=1;i<=N;i++) U[i]=0; maxPath=0;
  30.   for(int i=1;i<=N;i++) if(U[i]==0) DFS_R(i);
  31. }
  32.  
  33. int main()
  34. {  
  35.     int x,y,i;
  36.     cin >> N >> M;
  37.    
  38.     for(i=1;i<=N;i++) G[i][0]=0;
  39.    
  40.     for(i=1;i<=M;i++)
  41.     {  
  42.        cin >> x >> y;
  43.        G[x][++G[x][0]]=y;
  44.     }
  45.    
  46.     first_call();
  47.    
  48.     cout << maxPath << endl;
  49.    
  50.     return EXIT_SUCCESS;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment