fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define M 1000000007
  5.  
  6. #define mp make_pair
  7. #define pb push_back
  8. #define tri pair<int, pair<int, int> >
  9. #define TRI(a,b,c) (make_pair(a,make_pair(b,c)))
  10.  
  11. typedef long long ll;
  12. typedef long double ld;
  13.  
  14. int arr[100001], visited[100001], dp[100001];
  15.  
  16. vector<int> adj[100001], tvec;
  17.  
  18. void tsort(int i, int par)
  19. {
  20. 	visited[i]=1;
  21. 	for(int j=0; j<adj[i].size(); j++)
  22. 	{
  23. 		if(visited[adj[i][j]]==0)
  24. 		{
  25. 			tsort(adj[i][j], i);
  26. 		}
  27. 		else if(visited[adj[i][j]]==1)
  28. 		{
  29. 			cout<<-1;
  30. 			exit(0);
  31. 		}
  32. 	}
  33. 	visited[i]=2;
  34. 	tvec.pb(i);
  35. }
  36.  
  37. int dfs(int i, int col)
  38. {
  39. 	dp[i]=(arr[i]==col);
  40. 	int mx=0;
  41. 	for(int j=0; j<adj[i].size(); j++)
  42. 	{
  43. 		mx=max(mx,dp[adj[i][j]]);
  44. 	}
  45. 	dp[i]+=mx;
  46. 	return dp[i];
  47. }
  48.  
  49. int main() 
  50. {
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(NULL);
  53.     cout.tie(NULL);
  54.     int n, m;
  55.     cin>>n>>m;
  56.     for(int i=0; i<n; i++)
  57.     {
  58.     	cin>>arr[i];
  59.     	visited[i]=0;
  60.     }
  61.     for(int i=0; i<m; i++)
  62.     {
  63.     	int x, y;
  64.     	cin>>x>>y;
  65.     	if(x==y)
  66.     	{
  67.     		cout<<-1;
  68.     		return 0;
  69.     	}
  70.     	adj[x-1].pb(y-1);
  71.     }
  72.     for(int i=0; i<n; i++)
  73.     {
  74.     	if(visited[i]==0)
  75.     	{
  76.     		tsort(i, -1);
  77.     	}
  78.     }
  79.     int mx=1;
  80.     for(int i=1; i<=100; i++)
  81.     {
  82.     	for(int j=0; j<n; j++)
  83.     	{
  84. 	    	int ret = dfs(tvec[j], i);
  85. 	    	mx = max(mx, ret);
  86.     	}
  87.     }
  88.     cout<<mx;
  89.     return 0;
  90. }
Success #stdin #stdout 0s 5416KB
comments (?)
stdin
copy 
5 6
1 2 1 2 2
1 2
1 3
1 4
2 3
4 5
5 2
stdout
copy 
3
https://ideone.com/EMz4Ze
language:
C++14 (gcc 8.3)
created:
5 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!