fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define INF 1000000007
  5.  
  6. typedef long long ll;
  7. typedef unsigned long long ull;
  8. typedef vector<int> vi;
  9. typedef vector<ll> vll;
  10. typedef vector<vector<int> > vvi;
  11. typedef pair<int,int> ii;
  12. typedef vector<pair<int,int> > vii;
  13. typedef vector<vector<pair<int,int> > > vvii;
  14.  
  15. #define all(x) (x).begin(), (x).end()
  16. #define nall(x) (x).rbegin(), (x).rend()
  17. #define tr(x,it) for(auto it = (x).begin();it!=(x).end();++it)
  18. #define ntr(x,it) for(auto it = (x).rbegin();it!=(x).rend();++it)
  19. #define ufy(v) sort(all(v));(v).erase(unique(all((v))),(v).end())
  20. #define sz(a) int((a).size()) 
  21. #define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  22. #define pb push_back 
  23. #define PB pop_back
  24. #define pf push_front
  25. #define PF pop_front
  26. #define MP make_pair
  27. #define clr clear
  28. #define rz resize
  29. #define C(a,b) memset(a,b,sizeof(a))
  30. #define ia(a,n) FOR(i,0,n-1)cin>>a[i]
  31. #define ia1(a,n) FOR(i,1,n)cin>>a[i]
  32. #define fpresent(c,x) ((c).find(x) != (c).end())  // set,map
  33. #define present(c,x) (find(all(c),x) != (c).end())  //vector
  34. #define F first
  35. #define S second
  36. #define FOR(i,a,b) for(int i=a;i<=b;++i)
  37. #define NFOR(i,a,b) for(int i=a;i>=b;--i)
  38. #define rep(i,n) FOR(i,0,n-1)
  39. #define TCASE int __T;cin>>__T;FOR(Tc,1,__T)
  40. inline int add(int a,int b, int m=INF){a+=b;if(a>=m)a-=m;return a;}
  41. inline int mul(int a,int b, int m=INF){return (int)(((ll)a*(ll)b)%m);}
  42.  
  43.  
  44.  
  45. vii g[910];
  46. int d1[910];
  47. int d2[910];
  48. int ans[150010];
  49. int vis[910];
  50. int son[910];
  51. queue<pair<ii,int> > q;
  52. int main()
  53. {
  54.     boost;
  55.     int n,m;
  56.     while(cin>>n)    
  57.     {
  58.         if(n==0)break;
  59.         cin>>m;
  60.         FOR(i,0,n-1)g[i].clr();
  61.         FOR(i,0,m-1)
  62.         {
  63.             int x,y;
  64.             cin>>x>>y;
  65.             g[x-1].pb({y-1,i});
  66.             ans[i]=0;
  67.         }
  68.         FOR(i,0,n-1)
  69.         {
  70.             FOR(j,0,n-1)d1[j]=d2[j]=INF,vis[j]=-1,son[j]=0;
  71.  
  72.             tr(g[i],it)son[it->F]=1;
  73.  
  74.             q.push(MP(MP(i,0),-1));
  75.             d1[0]=0;
  76.             while(!q.empty())
  77.             {
  78.                 int now=q.front().F.F;
  79.                 int d=q.front().F.S;
  80.                 int par=q.front().S;
  81.                 q.pop();
  82.                 if(now==i)
  83.                 {
  84.                     if(vis[now]==-1)vis[now]++;
  85.                     else continue;
  86.                 }
  87.  
  88.                 else if(vis[now]==-1)
  89.                 {
  90.                     d1[now]=d;vis[now]=par;
  91.                 }
  92.                 else if(vis[now]!=-1 and vis[now]!=INF and vis[now]!=par)
  93.                 {
  94.                     d2[now]=d;vis[now]=INF; 
  95.                 }
  96.                 else continue;
  97.  
  98.                 tr(g[now],it)
  99.                 {
  100.                     q.push(MP(MP(it->F,d+1),(now==i)?it->F:par));
  101.                 }
  102.             }
  103.             tr(g[i],it)
  104.             {
  105.                 if(d2[it->F]!=INF)
  106.                 ans[it->S]=d2[it->F];
  107.             }
  108.         }
  109.  
  110.             FOR(i,0,m-1)
  111.             cout<<ans[i]<<" ";
  112.             cout<<"\n";
  113.     }
  114.     return 0;
  115. }
Success #stdin #stdout 0s 4064KB
comments (?)
stdin
copy 
3 3
1 2
2 3
1 3
3 3
1 2
2 1
1 3
3 6
1 2
2 1
1 3
3 1
3 2
2 3
stdout
copy 
0 0 2 
0 0 0 
2 2 2 2 2 2
https://ideone.com/sCOHAQ
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!