Advertisement
Guest User

Untitled

a guest
Aug 30th, 2014
4,299
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. const int NMAX = 1010;
  8.  
  9. int N, K, V[10][NMAX], Pos[10][NMAX], Best[NMAX], Ans;
  10. vector<int> G[NMAX];
  11. bool Used[NMAX];
  12.  
  13. void DFS(int Node)
  14. {
  15. Used[Node] = 1;
  16. for(int i = 0; i < G[Node].size(); ++ i)
  17. {
  18. if(!Used[G[Node][i]])
  19. DFS(G[Node][i]);
  20. Best[Node] = max(Best[Node], Best[ G[Node][i] ] + 1);
  21. }
  22. Best[Node] = max(Best[Node], 1);
  23. Ans = max(Ans, Best[Node]);
  24. }
  25.  
  26. int main()
  27. {
  28. // freopen("d.in", "r", stdin);
  29. // freopen("d.out", "w", stdout);
  30.  
  31. scanf("%i %i", &N, &K);
  32. for(int i = 1; i <= K; ++ i)
  33. for(int j = 1; j <= N; ++ j)
  34. {
  35. scanf("%i", &V[i][j]);
  36. Pos[i][ V[i][j] ] = j;
  37. }
  38.  
  39. for(int i = 1; i <= N; ++ i)
  40. for(int j = 1; j <= N; ++ j)
  41. {
  42. if(i == j) continue;
  43. bool OK = 1;
  44. for(int k = 1; k <= K; ++ k)
  45. if(Pos[k][i] >= Pos[k][j])
  46. OK = 0;
  47. if(OK) G[i].push_back(j);
  48. }
  49.  
  50. for(int i = 1; i <= N; ++ i)
  51. if(!Used[i])
  52. DFS(i);
  53.  
  54. printf("%i\n", Ans);
  55. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement