fork download
copy 
  1. /*
  2. Author : Chandan Agrawal
  3. College : Poornima College of Engg. jaipur, Raj
  4. Mail : chandanagrawal23@gmail.com
  5.  
  6.  
  7. " when you are not practicing someone else is ,
  8.  and the day u meet them u will lose "
  9.  
  10. */
  11. #include<bits/stdc++.h>
  12. #include<stdio.h>
  13. using namespace std;
  14.  
  15. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  16. #define MAX 300050
  17.  
  18. #define ll long long
  19. #define ld long double
  20. #define lli long long int
  21.  
  22. #define pb push_back
  23. #define INF 1000000000000
  24. #define mod 1000000007
  25.  
  26. // trignometric function always give value in Radians only
  27. #define PI acos(-1) //3.1415926535897932384626433832795028
  28. #define dsin(degree) sin(degree*(PI/180.0))
  29. #define dcos(degree) cos(degree*(PI/180.0))
  30. #define dtan(degree) tan(degree*(PI/180.0))
  31.  
  32. #define rsin(radian) sin(radian)
  33. #define rcos(radian) cos(radian)
  34. #define rtan(radian) tan(radian)
  35.  
  36. #define mem0(a) memset(a,0,sizeof(a))
  37. #define mem1(a) memset(a,-1,sizeof(a))
  38. #define memf(a) memset(a,false,sizeof(a))
  39.  
  40. #define loop(i,n)  for (lli i = 0; i < n; i++)
  41. #define FOR(i,a,b) for (lli i = a; i < b; i++)
  42.  
  43. #define all(v) v.begin(),v.end()
  44. #define rall(v) v.rbegin(),v.rend()
  45. #define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
  46. #define sz(x) int(x.size())
  47. #define F first
  48. #define S second
  49.  
  50. #define mii map<lli,lli>
  51.  
  52. #define pii pair<lli,lli>
  53.  
  54. #define vi vector<lli>
  55. #define vvi vector<vi>
  56. #define vpi vector<pii>
  57. #define vbool vector<bool>
  58.  
  59. #define seti set<lli>
  60.  
  61. #define gcd(a,b) __gcd((a),(b))
  62. #define lcm(a,b) (a/gcd(a,b))*b
  63. #define abs(x) ((x < 0)?-(x):x)
  64.  
  65. #define endl '\n'
  66.  
  67. template <typename Head>
  68. void print(Head&& head)
  69. {
  70.     cout<<head<<endl;
  71. }
  72. template <typename Head, typename... Tail>
  73. void print(Head&& head, Tail... tail)
  74. {
  75.     cout<<head<<" ";
  76.     print(tail...);
  77. }
  78.  
  79. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  80. #define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}
  81.  
  82. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  83. #define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  84.  
  85. #define FD(N) fixed<<setprecision(N)
  86.  
  87. #define deb(x) cout<<#x<<" "<<x<<endl;
  88.  
  89. /*
  90. 1D vector -  vi dp(n,value);
  91. 2D vector -  vvi dp(n,vi(n,value));
  92. */
  93.  
  94. // chandan1,2
  95. void chandan1(){int y=1;return;}
  96. void chandan2(){
  97.         loop(i,10){
  98.         lli x=1;
  99.     }
  100.     return(chandan1());
  101. }
  102.  
  103. //-------------------------------------------------------------GRAPH--------------------------------------------------------------------
  104.  
  105. int vis[MAX];
  106. vi adj[MAX];
  107. lli parent[MAX];
  108. lli depth[MAX];
  109. lli dp[MAX];//subtree size
  110. lli color[MAX];
  111. lli cnt=0;
  112. lli indegree[MAX];
  113.  
  114. void clear(lli n)
  115. {
  116.     loop(i,n+1)
  117.     {
  118.         vis[i]=0;
  119.         adj[i].clear();
  120.         parent[i]=0;
  121.         depth[i]=0;
  122.         dp[i]=0;
  123.     }
  124. }
  125.  
  126. void dfs(lli src)
  127. {
  128.     vis[src]=1;
  129.     dp[src]=1;
  130.     cnt+=1;
  131.     for(auto xt : adj[src])
  132.     {
  133.         if(!vis[xt])
  134.         {
  135.             dfs(xt);
  136.             dp[src]+=dp[xt];
  137.         }
  138.     }
  139. }
  140.  
  141. bool bfs(lli src)
  142. {
  143.     vis[src]=1;
  144.     queue<lli>q;
  145.     q.push(src);
  146.     depth[src]=0;
  147.     parent[src]=src;
  148.     color[src]=1;
  149.     while(!q.empty())
  150.     {
  151.         lli u = q.front();q.pop();
  152.         for(auto xt : adj[u])
  153.         {
  154.             if(!vis[xt])
  155.             {
  156.                 vis[xt]=1;
  157.                 q.push(xt);
  158.                 parent[xt]=u;
  159.                 depth[xt] = depth[u]+1;
  160.                 color[xt] = 1-color[u];
  161.             }
  162.             if(color[xt] == color[u])
  163.                 return false;
  164.         }
  165.     }
  166.     return true;
  167. }
  168.  
  169. //https://g...content-available-to-author-only...b.com/chandanagrawal23/Data-Structures/blob/master/Topological%20Sort_BFS
  170.  
  171. // we can use either queue or priority que a/c to question
  172.  
  173. // if sz(ans) != v then it means it contains cycle
  174.  
  175.  
  176.  
  177. vi toposort(lli n){
  178.  
  179.     //priority_queue<lli , vi , greater<int> > pq;
  180.  
  181.     queue<lli> pq;
  182.  
  183.     vi ans;
  184.  
  185.     for(lli i=1;i<=n;i++)
  186.         if(indegree[i] == 0)
  187.             pq.push(i);
  188.  
  189.     while(!pq.empty())
  190.     {
  191.  
  192.         lli cur = pq.front();
  193.         ans.pb(cur);
  194.         pq.pop();
  195.  
  196.         for(auto node : adj[cur])
  197.         {
  198.             indegree[node]--;
  199.             if(indegree[node]==0)
  200.                 pq.push(node);
  201.  
  202.         }
  203.  
  204.  
  205.     }
  206.  
  207.  
  208.     return ans;
  209.  
  210. }
  211.  
  212.  
  213. //-------------------------------------------------------------GRAPH--------------------------------------------------------------------
  214.  
  215.  
  216.  
  217. int main(){
  218. fastio
  219. lli t=1;
  220. //cin>>t;
  221. chandan2();
  222. while(t--) {
  223.     lli n,m,k;
  224.     cin>>n>>m;
  225.     loop(i,m)
  226.     {
  227.         lli x,y;
  228.         cin>>x>>y;
  229.         adj[x].pb(y);
  230.         indegree[y]++;
  231.     }
  232.  
  233.     vi topo_order = toposort(n);
  234.  
  235.     if(sz(topo_order)!=n) //if cycle is present then answer will be infinite so that print -1
  236.         print("IMPOSSIBLE");
  237.     else
  238.     {
  239.         lli dist[n+1]={0};
  240.         lli parent[n+1];
  241.         FOR(i,1,n+1)
  242.             parent[i] = i;
  243.         for(auto x : topo_order)
  244.         {
  245.             for(auto y : adj[x])
  246.             {
  247.                 if(dist[y]<(dist[x]+1))
  248.                 {
  249.                     dist[y] = dist[x]+1;
  250.                     parent[y] = x;
  251.                 }
  252.             }
  253.         }
  254.  
  255.         vi ans;
  256.         ans.pb(n);
  257.         while(parent[n]!=n)
  258.         {
  259.             n = parent[n];
  260.             ans.pb(n);
  261.         }
  262.         reverse(all(ans));
  263.         if(ans[0]==1)
  264.         {
  265.             print(sz(ans));
  266.             printvec(ans);
  267.         }
  268.  
  269.         else
  270.             print("IMPOSSIBLE");
  271.  
  272.     }
  273.  
  274.   }
  275. return 0;
  276. }
  277.  
Success #stdin #stdout 0s 10676KB
comments (?)
stdin
copy 
5 5
1 2
2 5
1 3
3 4
4 5
stdout
copy 
4
1 3 4 5
https://ideone.com/657nFB
language:
C++ (gcc 8.3)
created:
4 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!