fork download
copy 
  1. /**
  2.  * created by : Mostafa Wael (Phoenix)
  3.  * problem name : shortest cycle 
  4.  */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. int bfs(int source,int n,vector<long long>&v){
  8.     vector<int>distance(n,-1),parent(n,-1);
  9.     distance[source] = 0;
  10.     queue<int>q;
  11.     q.push(source);
  12.     while(!q.empty()){
  13.         int x=q.front(); q.pop();
  14.         for(int y=0;y<n;y++){
  15.             // y == x self cycle invalid , parent [x] == y cycle like 1->2->1 invalid , v[x]&v[y]==0 there is not edge between two nodes
  16.             if(y==x||parent[x]==y||!(v[y]&v[x])) continue;
  17.             if(~distance[y]) return distance[y]+distance[x]+1;// length of cycle 
  18.             distance[y]=distance[x]+1;
  19.             parent[y]=x;
  20.             q.push(y);
  21.         }
  22.     }
  23.     return 125;
  24. }
  25. int main()
  26. {
  27.     ios::sync_with_stdio(0);
  28.     cin.tie(0);
  29.     cout.tie(0);
  30.     /**
  31.      *  if i want to make an edge between two node then (&) between them at least = 1 -> (1) 
  32.      *  for example : (worst case)
  33.      *  0.....000000000000001
  34.      *  0.....000000000000001
  35.      *  0.....000000000000010
  36.      *  0.....000000000000010
  37.      *  0.....000000000000100
  38.      *  0.....000000000000100
  39.      *  ... 
  40.      *  10......0000000000000
  41.      *  100.....0000000000000
  42.      *  log2(10^18) = 60 -> (2)
  43.      *  from (1) and (2) 
  44.      *  if the n is greater than 120 the answer should be = 3 (smallest cycle ex: 1->2->3->1)
  45.      *  otherwise we can calculate it using BFS 
  46.      */
  47.     int n,ans=121; cin>>n;
  48.     vector<long long> v;
  49.     for(int i=0;i<n;i++){
  50.         long long u;
  51.         cin>>u;
  52.         if(u){// corner case 
  53.             if(v.size()<121) v.push_back(u);
  54.             else {
  55.                 cout<<3;
  56.                 return 0;
  57.             }
  58.         }
  59.     }
  60.     n=v.size();
  61.     for(int i=0;i<n;i++)
  62.     ans=min(ans,bfs(i,n,v));
  63.     cout<<(ans==121?-1:ans);
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.01s 5352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/a3a5dW
language:
C++ (gcc 8.3)
created:
2 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!