Shortest Cycle in a Graph

findShortestCycle.cpp

class Solution {
public:
    typedef vector<set<int>> t_graph; 
    int findShortestCycle(int n, vector<vector<int>>& edges) {
        t_graph a(n);
        for(auto&ex:edges){
            a[ex[0]].insert(ex[1]);
            a[ex[1]].insert(ex[0]);
        }
        vector<int> passed(n,-1e9);
        auto result=findShortestCycleV2(a,passed,false);
        return result==INT_MAX?-1:result;
    }
    void findShortestCycleInBoroda(t_graph&a,vector<int>&passed,int&best,set<int>&se,int dv){
        int n=a.size();
        vector<int> c(n),s(n,-1e9);
        map<int,set<int>> front,next;
        int color=1;
        vector<int> sev;
        for(auto&ex:se){
          next[ex].insert(ex);c[ex]=color++;sev.push_back(ex);
        }
        for(int t=1;next.size();t++){
            front=std::move(next);
            for(auto&f:front){
                for(auto&ex:a[f.first]){
                    auto&p=passed[ex];auto&v=c[ex];auto&pt=passed[f.first];auto&pc=c[f.first];
                    auto&sex=s[ex];if(sex<0)sex=t;
                    if(p<0||p>pt)continue;
                    auto&ey=f.first;
                    bool start_link=se.count(ey)&&se.count(ex);
                    if(dv&&start_link){
                      best=3;return;
                    }
                    if(!start_link)if(v&&v!=pc){
                      auto need_sub=pt==p;
                      if(need_sub){
                        int gg=1;
                      }
                      auto q2=sex+t+1+(need_sub?0/*-1*/:0);
                      auto q=t*2+1+(pt==p?1:0);
                      best=min(best,min(q,q2)+dv);
                      return;
                    }
                    if(v)continue;
                    v=pc;
                    next[ex].insert(f.first);
                }
            }
        }
        return;
    }
    int findShortestCycleV2(t_graph&a,vector<int>&psd,bool inside){
        int n=a.size();int best=INT_MAX;int dir=inside?-1:+1;
        vector<int> passed_buff(n,-1e9);
        for(int id=inside?a.size()-1:0;inside?id>=0:id<a.size();id+=dir){
            if(inside){if(psd[id]==-1e9)continue;}else if(psd[id]!=-1e9)continue;
            vector<t_graph> t2a(1);//t2a.reserve(16);
            map<int,set<int>> front,next;
            auto&passed=inside?passed_buff:psd;
            if(a[id].empty())continue;
            next[id].insert(id);passed[id]=1;
            for(int t=1;next.size();t++){
                t2a.push_back(t_graph(n));
                auto&g=t2a[t];int edges=0;
                front=std::move(next);
                for(auto&f:front){
                    if(inside){
                        int gg=1;
                    }
                    for(auto&ex:a[f.first]){
                        auto&p=passed[ex];
                        if(!(p<0||p==t+1||p==t))continue;
                        if(p==t){
                          edges++;
                          auto b=f.first;auto e=ex;
                          set<int> se{b,e};
                          findShortestCycleInBoroda(a,passed,best,se,0);
                          if(best<=3)return 3;
                        }
                        g[f.first].insert(ex);
                        g[ex].insert(f.first);
                        if(p!=t)next[ex].insert(f.first);
                        if(p!=t)p=t+1;
                    }
                }
                for(auto&ex:next){
                    auto&b=ex.first;
                    auto&arr=ex.second;
                    if(arr.size()>=2){
                      findShortestCycleInBoroda(a,passed,best,arr,1);
                      if(best<=3)return 3;
                    }
                }
                if(best<=3)return 3;
                if(edges>2){
                  if(g!=a)best=min(best,findShortestCycleV2(g,passed,true));
                }
                if(best<=3)return 3;
            }
        }
        return best;
    }
};