图论算法模板整理

//无向图的双连通分量
int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt; // 割顶的bccno无意义
struct Edge { int u, v; };
vector<int> G[maxn], bcc[maxn];

stack<Edge> S;

int dfs(int u, int fa) 
{
  int lowu = pre[u] = ++dfs_clock;
  int child = 0;
  for(int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    Edge e = (Edge){u, v};
    if(!pre[v]) { // 没有访问过v
      S.push(e);
      child++;
      int lowv = dfs(v, u);
      lowu = min(lowu, lowv); // 用后代的low函数更新自己
      if(lowv >= pre[u]) {
        iscut[u] = true;
        bcc_cnt++; bcc[bcc_cnt].clear();
        for(;;) {
          Edge x = S.top(); S.pop();
          if(bccno[x.u] != bcc_cnt) { bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt; }
          if(bccno[x.v] != bcc_cnt) { bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt; }
          if(x.u == u && x.v == v) break;
        }
      }
    }
    else if(pre[v] < pre[u] && v != fa) {
      S.push(e);
      lowu = min(lowu, pre[v]); // 用反向边更新自己
    }
  }
  if(fa < 0 && child == 1) iscut[u] = 0;
  return lowu;
}

void find_bcc(int n) {
  // 调用结束后S保证为空，所以不用清空
  memset(pre, 0, sizeof(pre));
  memset(iscut, 0, sizeof(iscut));
  memset(bccno, 0, sizeof(bccno));
  dfs_clock = bcc_cnt = 0;
  for(int i = 0; i < n; i++)
    if(!pre[i]) dfs(i, -1); 
};

//无向图求桥 & 双连通分量
int dfs(int u, int fa)  
{  
    int lowu = pre[u] = ++dfs_clock;  
    int nc = G[u].size();  
    REP(i, nc)  
    {  
        int v = edges[G[u][i]].to;  
        if(!pre[v])  
        {  
            int lowv = dfs(v, u);  
            lowu = min(lowu, lowv);  
            if(lowv > pre[u]) edges[G[u][i]].flag = 1, edges[G[u][i]^1].flag = 1; //标记所有桥  
        }  
        else if(pre[v] < pre[u] && v != fa) lowu = min(lowu, pre[v]);  
    }  
    return low[u] = lowu;  
}  
  
void dfs1(int u)  
{  
    bccno[u] = bcc_cnt;  
    int nc = G[u].size();  
    REP(i, nc)  
    {  
        int v = edges[G[u][i]].to;  
        if(!bccno[v] && edges[G[u][i]].flag != 1) dfs1(v);//不经过桥  
    }  
}  
  
void find_bcc()  
{  
    CLR(pre, 0); CLR(bccno, 0);  
    dfs_clock = bcc_cnt = 0;  
    REP(i, n) if(!pre[i]) dfs(i, -1);  
    REP(i, n) if(!bccno[i]) bcc_cnt++, dfs1(i);  
}  


//有向图的强连通分量
vector<int> G[maxn];
int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
stack<int> S;

void dfs(int u) {
  pre[u] = lowlink[u] = ++dfs_clock;
  S.push(u);
  for(int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if(!pre[v]) {
      dfs(v);
      lowlink[u] = min(lowlink[u], lowlink[v]);
    } else if(!sccno[v]) {
      lowlink[u] = min(lowlink[u], pre[v]);
    }
  }
  if(lowlink[u] == pre[u]) {
    scc_cnt++;
    for(;;) {
      int x = S.top(); S.pop();
      sccno[x] = scc_cnt;
      if(x == u) break;
    }
  }
}

void find_scc(int n) 
{
  dfs_clock = scc_cnt = 0;
  memset(sccno, 0, sizeof(sccno));
  memset(pre, 0, sizeof(pre));
  for(int i = 0; i < n; i++)
    if(!pre[i]) dfs(i);
};

//无向图的欧拉回路 保存在G中
void add(int u, int v)
{
    g[u][v] = g[v][u] = 1; 
    degree[u]++, degree[v]++; 
}

void Euler()  
{  
    FF(i, 1, n+1) if(degree[i])  
    {  
        int u = i;  
        while(true)  
        {  
            FF(j, 1, n+1) if(g[u][j] && g[j][u])  
            {  
                g[j][u] = 0;  
                degree[u]--, degree[i]--;  
                u = j;  
                break;  
            }  
            if(u == i) break;  
        }  
    }  
} 

//2-sat dfs版本
struct TwoSAT {
  int n;
  vector<int> G[maxn*2];
  bool mark[maxn*2];
  int S[maxn*2], c;

  bool dfs(int x) {
    if (mark[x^1]) return false;
    if (mark[x]) return true;
    mark[x] = true;
    S[c++] = x;
    for (int i = 0; i < G[x].size(); i++)
      if (!dfs(G[x][i])) return false;
    return true;
  }

  void init(int n) {
    this->n = n;
    for (int i = 0; i < n*2; i++) G[i].clear();
    memset(mark, 0, sizeof(mark));
  }

  // x = xval or y = yval
  void add_clause(int x, int xval, int y, int yval) {
    x = x * 2 + xval;
    y = y * 2 + yval;
    G[x^1].push_back(y);
    G[y^1].push_back(x);
  }

  bool solve() {
    for(int i = 0; i < n*2; i += 2)
      if(!mark[i] && !mark[i+1]) {
        c = 0;
        if(!dfs(i)) {
          while(c > 0) mark[S[--c]] = false;
          if(!dfs(i+1)) return false;
        }
      }
    return true;
  }
};

//堆优化的Dijkstra
struct Edge {
  int from, to, dist;
};

struct HeapNode {
  int d, u;
  bool operator < (const HeapNode& rhs) const {
    return d > rhs.d;
  }
};

struct Dijkstra {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool done[maxn];    // 是否已永久标号
  int d[maxn];        // s到各个点的距离
  int p[maxn];        // 最短路中的上一条弧

  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }

  void dijkstra(int s) {
    priority_queue<HeapNode> Q;
    for(int i = 0; i < n; i++) d[i] = INF;
    d[s] = 0;
    memset(done, 0, sizeof(done));
    Q.push((HeapNode){0, s});
    while(!Q.empty()) {
      HeapNode x = Q.top(); Q.pop();
      int u = x.u;
      if(done[u]) continue;
      done[u] = true;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          Q.push((HeapNode){d[e.to], e.to});
        }
      }
    }
  }

  // dist[i]为s到i的距离，paths[i]为s到i的最短路径（经过的结点列表，包括s和t）
  void GetShortestPaths(int s, int* dist, vector<int>* paths) {
    dijkstra(s);
    for(int i = 0; i < n; i++) {
      dist[i] = d[i];
      paths[i].clear();
      int t = i;
      paths[i].push_back(t);
      while(t != s) {
        paths[i].push_back(edges[p[t]].from);
        t = edges[p[t]].from;
      }
      reverse(paths[i].begin(), paths[i].end());
    }
  }
};

//spfa判负环
struct Edge {
  int from, to;
  double dist;
};

struct spfa {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];     // 是否在队列中
  double d[maxn];     // s到各个点的距离
  int p[maxn];        // 最短路中的上一条弧
  int cnt[maxn];      // 进队次数

  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  void AddEdge(int from, int to, double dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }

  bool negativeCycle() {
    queue<int> Q;
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < n; i++) { d[i] = 0; inq[0] = true; Q.push(i); }

    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      inq[u] = false;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
        }
      }
    }
    return false;
  }
};


//kruskal求次小生成树 maxcost[i][j]为i->j的瓶颈路 
//对于MST边u, v maxcost[u][v] = 0
int n, m, x[maxn], y[maxn], p[maxn];
int pa[maxn];
int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; } 
//G保存MST C保存MST边权
vector<int> G[maxn];
vector<double> C[maxn];
struct Edge {
  int x, y;
  double d;
  bool operator < (const Edge& rhs) const {
    return d < rhs.d;
  }
};

Edge e[maxn*maxn];
double maxcost[maxn][maxn];
vector<int> nodes;

void dfs(int u, int fa, double facost) {
  for(int i = 0; i < nodes.size(); i++) {
    int x = nodes[i];
    maxcos
补充：软件开发 , C++ ,

上一个：UVa 10837 A Research Problem 欧拉函数
下一个：hdu 3030 Increasing Speed Limits（树状数组求最长上升子序列）