• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added lib/graph/dfa_hopcroft.cpp version [7827709f822d3c66]

            1  +// TODO : optimize to O(n log n)
            2  +//  current version looks to be running in O(n^2) ... orz
            3  +//
            4  +// TODO : clean up as a library
            5  +//
            6  +// Copy&Paste from SRM562 Div1 Hard
            7  +
            8  + // Input is given as:
            9  + //    v----c---->G[v][c]
           10  + // Must be a complete automaton.
           11  + // !!! The following code is assuming |c|==4 !!!
           12  + //
           13  + // !!! The following code is assuming the final state is {0}.
           14  + //
           15  + mint solve(vector< vector<int> >& G)
           16  + {
           17  +  vector< vector<int> > set_buffer;
           18  +  set<int> active_sets;
           19  +  set<int> active_splitters;
           20  +
           21  +  {
           22  +   set_buffer.push_back( vector<int>(1,0) );
           23  +   vector<int> all;
           24  +   for(int v=1; v<G.size(); ++v)
           25  +    all.push_back(v);
           26  +   set_buffer.push_back(all);
           27  +
           28  +   active_sets.insert(0);
           29  +   active_sets.insert(1);
           30  +   active_splitters.insert(0);
           31  +  }
           32  +
           33  +  while(!active_splitters.empty())
           34  +  {
           35  +   const vector<int>& splv = set_buffer[*active_splitters.begin()];
           36  +   set<int> spl(splv.begin(), splv.end());
           37  +   active_splitters.erase(active_splitters.begin());
           38  +
           39  +   for(int d=0; d<4; ++d)
           40  +   for(set<int>::iterator it=active_sets.begin(); it!=active_sets.end(); )
           41  +   {
           42  +    int ii = *it++;
           43  +    const vector<int>& cur = set_buffer[ii];
           44  +    vector<int> t, f;
           45  +    for(int k=0; k<cur.size(); ++k)
           46  +     (spl.count(G[cur[k]][d]) ? t : f).push_back(cur[k]);
           47  +    if(!t.empty() && !f.empty())
           48  +    {
           49  +     set_buffer.push_back(t);
           50  +     set_buffer.push_back(f);
           51  +     active_sets.insert(set_buffer.size()-2);
           52  +     active_sets.insert(set_buffer.size()-1);
           53  +     if(active_splitters.count(ii)) {
           54  +      active_splitters.insert(set_buffer.size()-2);
           55  +      active_splitters.insert(set_buffer.size()-1);
           56  +     } else {
           57  +      active_splitters.insert(t.size()<f.size() ? set_buffer.size()-2 : set_buffer.size()-1);
           58  +     }
           59  +     active_splitters.erase(ii);
           60  +     active_sets.erase(ii);
           61  +    }
           62  +   }
           63  +  }
           64  +
           65  +  vector<int> es;
           66  +  for(set<int>::iterator it=active_sets.begin(); it!=active_sets.end(); ++it)
           67  +   if(*it)
           68  +    es.push_back(set_buffer[*it].size());
           69  +/*
           70  +  for(bool changed=true; changed;)
           71  +  {
           72  +   changed=false;
           73  +   for(int i=0; i<eqs.size(); ++i) if(!eqs[i].second && !dead[i]){
           74  +    set<int> spl(eqs[i].first.begin(), eqs[i].first.end());
           75  +    eqs[i].second = true;
           76  +    for(int k=0; k<eqs.size(); ++k)
           77  +    for(int d=0; d<4; ++d) if(!dead[k]) {
           78  +     vector<int> t, f;
           79  +     for(vector<int>::iterator it=eqs[k].first.begin(); it!=eqs[k].first.end(); ++it)
           80  +      (spl.count(G[*it][d]) ? t : f).push_back(*it);
           81  +     if(!t.empty() && !f.empty()) {
           82  +      if(eqs[k].second) {
           83  +       eqs.push_back(make_pair(t,t.size()>f.size()));
           84  +       eqs.push_back(make_pair(f,t.size()<=f.size()));
           85  +       dead.push_back(false);
           86  +       dead.push_back(false);
           87  +       changed = true;
           88  +      } else {
           89  +       eqs.push_back(make_pair(t,false));
           90  +       eqs.push_back(make_pair(f,false));
           91  +       dead.push_back(false);
           92  +       dead.push_back(false);
           93  +       changed = true;
           94  +      }
           95  +      dead[k] = true;
           96  +     }
           97  +    }
           98  +   }
           99  +  }
          100  +
          101  +  vector<int> es;
          102  +  for(int i=1; i<eqs.size(); ++i) if(!dead[i])
          103  +   es.push_back(eqs[i].first.size());
          104  +*/
          105  +  int sum = accumulate(es.begin(), es.end(), 0);
          106  +  mint x = POW(2, sum);
          107  +  for(int i=0; i<es.size(); ++i)
          108  +   x -= POW(2, es[i])-1;
          109  +  return x-1;
          110  + }
          111  +