graphcpp.cpp

acm 常用算法和代码库

#include <list>
#include <iostream>
#define maxV 100
#define INF 1000000
using namespace std;
using std::list; 
template <class T>  
    struct GraphList  { 
         int  v; 
         int  e; 
         list <T>  a[maxV];  // 邻接表  
         void  clear()       // clear()应在更改v之前进行  
         { 
             int  i; 
             for (i = 0 ; i < v; i ++ ) 
                a[i].clear(); 
         }  
         ~GraphList()  
         {  
            v = maxV; 
            clear(); 
         }  
};
template <class  T>  
      struct  GraphMatrix  { 
         int  v;     // 顶点数  
         int  e;     // 边数  
         T a[maxV][maxV];     // 邻接矩阵  
         void  init()  
         { 
            memset(a, 0 , sizeof (a)); 
         }  
         void  clear()  
         { 
             int  i,j; 
             for (i = 0 ; i < v;  ++ i) { 
                 for (j = 0 ; j < v;  ++ j) 
                    a[i][j] = INF; 
            }  
        }  
} ; 

namespace  GabowNS  { 
 /**/ /* 解决：强分量 
 *算法：Gabow——O(E) 
 *输入：图(表)：g 
 *输出：分量编号sc[] 
  */  
       
      int  cnt0, cnt1; 
      int  sc[maxV]; // 分量编号  
      int  pre[maxV];     // DFS顺序  
      int  path[maxV],pp; // path栈  
      int  stack[maxV],sp; // 栈  
  
      void  _SCdfsR( int  w,GraphList < int >  g)  { 
        pre[w] = cnt0 ++ ; 
        stack[sp ++ ] = w; 
        path[pp ++ ] = w; 
         int  v; std::list < int > ::iterator li; 
         for (li = g.a[w].begin(); li != g.a[w].end();  ++ li)  { 
            v =* li; 
             if (pre[v] ==- 1 ) _SCdfsR(v,g); 
             else   if (sc[v] ==- 1 )  { 
                 while (pre[path[pp - 1 ]]  >  pre[v])  -- pp; 
            }  
        }
         if (path[pp - 1 ]  !=  w)  return ; 
         -- pp; 
         do  { 
            sc[stack[ -- sp]] = cnt1; 
        } while (stack[sp]  !=  w); 
         ++ cnt1; 
      }  
      void  init(GraphList < int >  g)  { 
        memset(pre, - 1 , sizeof (pre)); 
        memset(sc, - 1 , sizeof (sc)); 
        cnt0 = cnt1 = 0 ; 
        sp = pp = 0 ; 
         int  i; 
         for (i = 0 ; i < g.v;  ++ i)  { 
             if (sc[i] ==- 1 ) 
                _SCdfsR(i,g); 
        }  
    }  
  
      bool  isStrongReach( int  s,  int  t,GraphList < int >  g)  { 
         return  sc[s] == sc[t]; 
    }  
}  

namespace  bridgeNS  { 
 
 int  cnt; 
 int  pre[maxV];     // DFS顺序  
 int  low[maxV];     // 最低前序编号：儿子low值的最小值  
 void  _bridge( int  prnt,  int  w,GraphList < int >  g)  
 { 
     int  v; // son  
     low[w] = pre[w] = cnt ++ ; 
     std::list < int > ::iterator li; 
     for (li = g.a[w].begin(); li != g.a[w].end();  ++ li)  { 
                v =* li; 
                 if (pre[v] ==- 1 )  { 
                    _bridge(w,v, g); 
                     if (low[w]  >  low[v]) low[w]  =  low[v]; 
                     if (low[v]  ==  pre[v]) 
                        printf( "  %d-%d\n" ,w+1,v+1); // 找到桥  
                 } else   if (v != prnt  &&  low[w]  >  pre[v]) low[w]  =  pre[v]; 
      }
 }  
 void  bridge(GraphList < int >  g)  { 
        cnt = 0 ; 
        memset(pre, - 1 , sizeof (pre)); 
        _bridge( - 1 , 0, g ); 
    }  
}

namespace  PrimNS  { 
 /**/ /* 解决：最小生成树MST 
 *算法：Prim——O(V^2) 
 *输入：加权连通图(矩阵)：g 
 *输出：父节点st[]，与其父之边的权重wt[] 
  */  
       
     int  st[maxV];     // MST节点之父——用以保存MST  
     double  wt[maxV + 1 ];     // 与其父的边的权重  
     int  fr[maxV];     // 非树顶点的最近树顶点
     int  mst(GraphMatrix < double >  g)  
     { 
         int  v, w, min; 
         for (v = 0 ; v < g.v;  ++ v)  { 
            st[v] =- 1 ; fr[v] = v; wt[v] = INF; 
        }//INIT  
        st[0] = 0 ; wt[g.v] = INF; 
         for (min = 0 ; min != g.v;)  { 
            v = min; st[v] = fr[v]; 
             for (w = 0 , min = g.v; w < g.v;  ++ w)  { 
                 if (st[w] ==- 1 )  { 
                     if (g.a[v][w]  <  wt[w]) 
                        wt[w] = g.a[v][w], fr[w] = v; 
                     if (wt[w]  <  wt[min]) 
                        min = w; 
                }  
            }  
        }  
    }  
}
namespace Dijkstra{
 /**/ /* 解决：非负权图单源最短路径树SPT 
 *算法：Dijkstra——O(V^2) 
 *输入：加权连通图(矩阵)：g 
 *输出：父节点st[]，与其父之边的权重wt[] 
  */   
     int  st[maxV];     
     double  wt[maxV + 1 ];     
     int  fr[maxV];     // 非树顶点的最近树顶点  
     void  spt( int  s,GraphMatrix < double >  g)  { 
         int  v, w, min; 
         for (v = 0 ; v < g.v;  ++ v)  { 
            st[v] =- 1 ; fr[v] = v; wt[v] = INF; 
        }  
        st[s] = s; wt[g.v] = INF; wt[s] = 0 ; 
         for (min = s; min != g.v;)  { 
            v = min; st[v] = fr[v]; 
             for (w = 0 , min = g.v; w < g.v;  ++ w)  { 
                 if (st[w] ==- 1 )  { 
                     if (g.a[v][w] != INF  &&  wt[v] + g.a[v][w]  <  wt[w]) 
                        wt[w] = wt[v] + g.a[v][w], fr[w] = v; 
                     if (wt[w]  <  wt[min]) 
                        min = w; 
                }  
             }  
        }  
    }  
}
namespace  TenshiNS  { // ，  
  /**/ /* 解决：二分图最大匹配 
 *算法：匈牙利匹配(by Tenshi)——O(xv * yv) 
 *输入：邻接矩阵g 
 *输出：匹配数cnt,x匹配项xm[]，y匹配项ym[] 
 *备注：from Bug 06-07-07 
  */  
      int  xv,yv;     // 顶点数  
      int  g[maxV][maxV];     // g[i][j]=1 表示 xi与yj相邻  
      int  sy[maxV];     // 辅助：当轮被搜过的y点都是1   
      int  cnt,xm[maxV],ym[maxV];  // 输出   
       void  init()  { 
        cnt = 0 ; 
        memset(g, 0 , sizeof (g)); 
        memset(xm, - 1 , sizeof (xm)); 
        memset(ym, - 1 , sizeof (ym)); 
     }  
     bool  _path( int  u) // 返回是否找到增广路  
     { 
         for ( int  v = 0 ;v < yv;v ++ )  if (g[u][v]  &&   ! sy[v])  
         { 
             sy[v] = 1 ; 
             if (ym[v] ==- 1 || _path(ym[v])){ xm[u] = v; ym[v] = u;  return   1 ;} 
         }   
         return   0 ;     
     }  
     void  tenshi() 
     { 
         int  i; 
         for (i = 0 ;i < xv;i ++ ) 
             if (xm[i] ==- 1 )  { 
                memset(sy, 0 , sizeof (sy)); 
                cnt += _path(i); 
            }  
    }   
} 


int main()
{
    GraphList<int> a;
    cin>>a.v>>a.e;
    a.clear();
    for(int i=0;i<a.e;i++)
    {
            int v,w;
            cin>>v>>w;
            v--;w--;
            a.a[v].push_back(w);
            //a.a[w].push_back(v);
    }
     
    
    //bridgeNS::bridge(a);
    GabowNS::init(a);
    for(int i=0;i<a.v;i++)
    {
            cout<<GabowNS::sc[i]<<" ";
    }
    system("pause");
}