fork download
copy 
  1. /*input
  2. 3 2
  3. 1 2
  4. 3 2
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define ll long long
  11. #define PII pair<ll, ll>
  12. #define f first
  13. #define s second
  14. #define F(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
  15. #define RF(i,a,b) for(ll i = (ll)(a); i >= (ll)(b); i--)
  16. #define inf LLONG_MAX
  17. #define mod 1000000007
  18. #define MAXN 100005
  19. #define pb(x) push_back(x)
  20.  
  21. ll n, m, u, v, ind=1, ans;
  22. vector<bool> vis;
  23. vector<vector<ll> > g;
  24. PII arr[MAXN];
  25. map < PII, ll > mp;
  26. stack < ll > st;
  27. ll tmp[MAXN];
  28. void dfs1(ll u)
  29. {
  30. 	ll sz=g[u].size();
  31. 	vis[u]=1;
  32. 	F(v,0,sz-1)
  33. 		if(!vis[g[u][v]])
  34. 			dfs1(g[u][v]);
  35. 	st.push(u);
  36. }
  37. void dfs2(ll u)
  38. {
  39. 	tmp[ind++]=u;
  40. 	vis[u]=1;
  41. 	ll sz=g[u].size();
  42. 	F(v,0,sz-1)
  43. 		if(!vis[g[u][v]])
  44. 			dfs2(g[u][v]);
  45. }
  46.  
  47. int main() 
  48. {
  49. 	ios_base::sync_with_stdio(false);cin.tie(0);
  50. 	cin>>n>>m;
  51.     g = vector<vector<ll> > (n+1); //initialization of the graph
  52.     vis = vector<bool> (n+1, 0); // initially mark all vertices as unvisited 
  53. 	F(i,1,m)
  54. 	{
  55. 		cin>>u>>v;
  56. 		g[u].pb(v);
  57. 		mp[{u,v}]=i;
  58. 	}	
  59. 	F(i,1,n)
  60. 	{
  61. 		if(!vis[i])
  62. 			dfs1(i);
  63.     }
  64.     vis = vector<bool> (n+1, 0); // initially mark all vertices as unvisited 
  65. 	while(!st.empty())
  66. 	{
  67. 		ll cur=st.top();
  68. 		st.pop();
  69. 		if(!vis[cur])
  70. 			dfs2(cur);
  71. 	}
  72. 	PII cur;
  73. 	bool flag=1;
  74. 	F(i,1,n-1)
  75. 	{
  76. 		cur.f=tmp[i];
  77. 		cur.s=tmp[i+1];
  78. 		if(mp[cur]==0)
  79. 		{
  80. 			flag=0;
  81. 			break;
  82. 		}
  83. 		ans=max(ans,mp[cur]);
  84. 	}
  85. 	if(flag)
  86. 		cout<<ans<<endl;
  87. 	else
  88. 		cout<<"-1"<<endl;
  89. 	return 0;
  90. }
Success #stdin #stdout 0s 5760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/sMWkUO
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!