Graph Connectivity

拓扑排序

满足限制条件的线性顺序，不唯一。

DAG的性质

• 入度为零的点：

  不与其他点连通。

  扩散信息时，至少要从所有入度为零的点开始扩散，才能扩散至全图。

• 出度为零的点：

  如果只有一个，则该点可以由其他所有点抵达。

• 添加多少边才能使DAG变为强连通图？

  max(入度零的点的个数，出度零的点的个数)

有向图

• 强连通：

  • \(v_i\)与\(v_j\)强连通：存在有向边\(v_i \rightarrow v_j\)与\(v_j \rightarrow v_i\)。
  • 强连通分量：极大强连通子图。

• Tarjan算法：DFS求有向图所有强连通分量。

  dfn: DFS’s index

  low: the lowest index that can be accessed starting from this point.

  dfn[u] == low[u]: u is the root (the first accessed point in DFS order.) of a strong connected component.

  Tarjan(int u):
      low[u] = dfn[u] = ++index;  # init
      stack.push(u);
      for each (u, v) in E:
        if not visited v:
            Tarjan(v);
            low[u] = min(low[u], low[v]); # obvious
        else if v in stack:
            low[u] = min(low[u], dfn[v]); # v's index is smaller than u
      if dfn[n] == low[n]:
        repeat:
            v = S.pop();
            print v;
        until u == v
  

• Kosaraju Algorithm

  (slower than tarjan)

• Examples

  • Popular Cows

    DAG中如果有唯一出度为零的节点，则它可以被所有其他节点访问到。

    把强连通分量均缩成一个点，则一个有向有环图可以转化为一个DAG。

    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <string>
    #include <vector>
    #include <set>
    #include <stack>
    using namespace std;
    
    const int maxn = 10005;
    vector<int> G[maxn];
    int dfn[maxn], low[maxn], color[maxn], vis[maxn], degree[maxn];
    int N, M, a, b;
    int ncolor = 0, idx = 0;
    stack<int> stk;
    
    void tarjan(int u) {
        dfn[u] = low[u] = idx++;
        vis[u] = 1;
        stk.push(u);
        int len = G[u].size();
        for (int i = 0; i < len; i++) {
            int v = G[u][i];
            if (!vis[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }
            else if (vis[v] == 1) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) {
            int v;
            do {
                v = stk.top(); stk.pop();
                color[v] = ncolor;  // dyeing
                vis[v] = 2;  // 1 means in stack, 2 means visited and out stack.
            } while (u != v); 
            ncolor++;
        }
    }
    
    int solve(){
        for(int i=1; i<=N; i++){
            int ci = color[i];
            for(int j=0; j<G[i].size(); j++)
                if(color[G[i][j]] != ci) degree[ci]++;
        }
        int end = -1;
        for(int i=0; i<ncolor; i++){
            if(degree[i]==0){
                if(end == -1) end = i;
                else return 0;
            }
        }
        int ans = 0;
        for(int i=1; i<=N; i++)
            if(color[i] == end) ans++;
        return ans;
    }
    
    int main() {
        cin >> N >> M;
        memset(color, -1, sizeof(color));
        for (int i = 0; i < M; i++) {
            cin >> a >> b;
            G[a].push_back(b);
        }
        for (int i = 1; i <= N; i++) {
            if (!vis[i]) tarjan(i);  // for separated points, we have to check all.
        }
        cout << solve() << endl;
    }
    

  • Network of Schools

    至少选取几个点才能遍历DAG所有顶点？入度为0的点个数。

    至少添加几条边才能使DAG强联通？max(入度0点个数，出度0点个数)

  • Going from u to v or v to u?

    半连通分量，仍然先把SCC缩成一个点，得到DAG。

    如果一个DAG的任意两点之间半连通，则DAG一定是一条线。

    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <string>
    #include <vector>
    #include <set>
    #include <stack>
    
    using namespace std;
    
    const int maxn = 1005;
    
    vector<int> G[maxn];
    int dfn[maxn], low[maxn], color[maxn], vis[maxn], outd[maxn], ind[maxn];
    
    int N, M, a, b;
    int ncolor = 0, idx = 0;
    
    void init(){
        for (int i = 1; i <= N; i++) G[i].clear();
        memset(color, -1, sizeof(color));
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(vis, 0, sizeof(vis));
        memset(outd, 0, sizeof(outd));
        memset(ind, 0, sizeof(ind));
        ncolor = 0;
        idx = 0;    
    }
    
    stack<int> stk;
    void tarjan(int u) {
        dfn[u] = low[u] = idx++;
        vis[u] = 1;
        stk.push(u);
        int len = G[u].size();
        for (int i = 0; i < len; i++) {
            int v = G[u][i];
            if (!vis[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }
            else if (vis[zh] == 1) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) {
            int v;
            do {
                v = stk.top(); stk.pop();
                color[v] = ncolor;
                vis[v] = 2;
            } while (u != v);
            ncolor++;
        }
    }
    
    bool solve(){
        for(int i=1; i<=N; i++){
            for(int j=0; j<G[i].size(); j++){
                if(color[G[i][j]] != color[i]) {
                    outd[color[i]]++;
                    ind[color[G[i][j]]]++;
                }
            }
        }
        // must be a linear graph
        for(int i=0; i<ncolor; i++){
            if(outd[i]>1 || ind[i]>1) return false;
        }
        return true;
    }
    
    int main() {
        int cas;
        cin>>cas;
        while(cas--){
            cin >> N >> M;
            init();
            for (int i = 0; i < M; i++) {
                cin >> a >> b;
                G[a].push_back(b);
            }
            for (int i = 1; i <= N; i++) {
                if (!vis[i]) tarjan(i);
            }
            cout << (solve()?"Yes":"No") << endl;
        }
    }
    

无向连通图

• 割点&桥

  删除该点/边后图不再连通。

• Tarjan Algorithm

  注意如果有重边，则桥的判断还需多加一步。

  #include <iostream>
  #include <algorithm>
  #include <vector>
  #include <stack>
  using namespace std;
  
  const int maxv = 100;
  const int maxe = 10000;
  
  struct edge {
    int f, t;
    edge() {}
    edge(int u, int v) :f(u), t(v) {}
    friend ostream& operator << (ostream& os, const edge& e) {
        os << "(" << e.f << " -> " << e.t << ")";
        return os;
    }
  };
  
  vector<edge> edges;
  vector<int> G[maxv];
  
  // directed
  void insert_edge(int a, int b) {
    edges.push_back(edge(a, b));
    int s = edges.size() - 1;
    G[a].push_back(s);
  }
  
  int dfn[maxv], low[maxv], vis[maxv], parent[maxv];
  int idx, N, M, nrs;
  
  void init() {
    idx = 0;
      nrs = 0; // n root sons
    memset(vis, 0, sizeof(vis));
    memset(parent, 0, sizeof(parent));
    for (int i = 0; i < maxv; i++) G[i].clear();
  }
  
  int iscut[maxv];
  int isbrd[maxe];
  
  // since there is no stack, we can use dfn[] as vis[] in fact.
  
  void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    vis[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = edges[G[u][i]].t;
        if (!vis[v]) {
              // undirected graph's DFS tree
            parent[v] = u;
               if(u==1) nrs++;
            tarjan(v);
            low[u] = min(low[u], low[v]);
            /* WHY cutvtx
            dfn[u] <= low[v] means subtree v can't point back 
            to vertices earlier than u.
            so if we remove u, subtree v is isolated.
            */
            if (dfn[u] <= low[v]) iscut[u] = 1;
            /* WHY bridge
            if dfn[u] == low[v], that edge has been in a loop,
              so deleting it can't separate the graph.
              low[u] != low[v] is also right.
            */
            if (dfn[u] < low[v]) {
                  // detect multiple edges.
                  int cnt = 0;
                  for(int j=0; j<G[u].size(); j++) if(edges[G[u][j]].t==v) cnt++;
                  if(cnt==1) isbrd[G[u][i]] = 1;
              }
        }
        // avoid undirected reverse edge: u <--*>* v
        else if (parent[u] != v) {
            low[u] = min(low[u], dfn[v]);  // must be dfn[v]
        }
    }
    // special for root !!!
    if (u == 1 && nrs < 2) iscut[u] = 0;
  }
  
  int main() {
    while (cin >> N >> M && N && M) {
        init();
        int a, b;
        for (int i = 0; i < M; i++) {
            cin >> a >> b;
            insert_edge(a, b);
            insert_edge(b, a);
        }
        tarjan(1);
        for (int i = 1; i <= N; i++) {
            if (iscut[i]) cout << i << endl;
        }
        for (int i = 0; i < M; i++) {
            if (isbrd[i]) cout << edges[i] << endl;
        }
    }
  }
  

  • example

    • Caocao’s Bridge

      巨坑无比。

      #include <iostream>
      #include <cstring>
      #include <algorithm>
      #include <vector>
      #include <stack>
      using namespace std;
      
      const int maxn = 1005;
      const int inf = 0x7fffffff;
      
      vector<int> G[maxn];
      
      int dfn[maxn], low[maxn], vis[maxn], parent[maxn];
      int w[maxn][maxn];
      int idx, N, M;
      
      void init() {
        idx = 0;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < maxn; i++) G[i].clear();
      }
      
      void tarjan(int u) {
        dfn[u] = low[u] = ++idx;
        vis[u] = 1;
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (!vis[v]) {
                parent[v] = u;
                tarjan(v);
                low[u] = min(low[u], low[v]);
            }
            else {
                if (parent[u] != v) low[u] = min(low[u], low[v]);
            }
        }
      }
      
      vector<pair<int, int>> brd;
      void bridge() {
        brd.clear();
        for (int i = 1; i <= N; i++) {
            int v = parent[i];
            if (dfn[v] < low[i]) {
                int cnt = 0;
                  // 重边检测
                for (int j = 0; j < G[v].size(); j++) if (G[v][j] == i) cnt++;
                if (cnt == 1) brd.push_back(make_pair(v, i));
            }
        }
      }
      
      int main() {
        while (cin >> N >> M && (N || M)) {
            init();
            int a, b, c;
            for (int i = 0; i < M; i++) {
                cin >> a >> b >> c;
                G[a].push_back(b);
                G[b].push_back(a);
                w[a][b] = w[b][a] = c;
            }
            tarjan(1);
              //不连接检测，直接返回0
            bool flag = false;
            for (int i = 1; i <= N; i++) {
                if (!vis[i]) {
                    cout << 0 << endl;
                    flag = true;
                    break;
                }
            }
            if (flag) continue;
            bridge();
              //无桥
            if (brd.empty()) {
                cout << -1 << endl;
                continue;
            }
            int ans = inf;
            for (int i = 0; i < brd.size(); i++) {
                a = brd[i].first;
                b = brd[i].second;
                c = w[a][b];
                ans = min(ans, c);
            }
              //至少一个人去炸桥
            cout << (ans == 0 ? 1 : ans) << endl;
        }
      }
      

• 点双连通分量（Biconnected Component）

  不包含割点的极大联通子图（块）。一个原图的割点可以属于多个点双连通分量，其他点与边只能属于一个。

  #include <iostream>
  #include <algorithm>
  #include <vector>
  #include <stack>
  using namespace std;
  
  const int maxv = 100;
  const int maxe = 10000;
  
  struct edge {
    int f, t;
    edge() {}
    edge(int u, int v) :f(u), t(v) {}
    friend ostream& operator << (ostream& os, const edge& e) {
        os << " (" << e.f << " -> " << e.t << ") ";
        return os;
    }
  };
  
  vector<edge> edges;
  vector<int> G[maxv];
  
  // directed
  void insert_edge(int a, int b) {
    edges.push_back(edge(a, b));
    int s = edges.size() - 1;
    G[a].push_back(s);
  }
  
  int dfn[maxv], low[maxv], vis[maxv], parent[maxv];
  int idx, N, M;
  
  void init() {
    idx = 0;
    memset(vis, 0, sizeof(vis));
    memset(parent, 0, sizeof(parent));
    for (int i = 0; i < maxv; i++) G[i].clear();
  }
  
  // edges stack
  stack<int> stk;
  void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    vis[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = edges[G[u][i]].t;
        if (!vis[v]) {
            stk.push(G[u][i]); // push new edge
            parent[v] = u;
            tarjan(v);
            low[u] = min(low[u], low[v]);
              // if u is cut vertex, there is a vertex-BCC
            if (dfn[u] <= low[v]) {
                cout << "BCC Block:" << endl;
                edge e;
                do {
                    e = edges[stk.top()];
                    stk.pop();
                    cout << e << endl;
                } while (!(e.f == u && e.t == v));
            }
        }
        else if (parent[u] != v) {
            low[u] = min(low[u], low[v]);
              // reverse edge to ancestor should be pushed. 
              // But to a child's edge must have been pushed earlier, so ignore it.
            if (dfn[u] > dfn[v]) stk.push(G[u][i]);
        }
    }
  }
  
  int main() {
    while (cin >> N >> M && N && M) {
        init();
        int a, b;
        for (int i = 0; i < M; i++) {
            cin >> a >> b;
            insert_edge(a, b);
            insert_edge(b, a);
        }
        tarjan(1);
    }
  }
  

• 边双连通分量

  不包含桥的极大联通子图，去掉所有桥即可。

  注意到，low数组本身已经是边双连通分量的一个染色。所以缩点甚至不用显示找出所有桥。

• Examples

  • Road Construction

    缩点为一棵树，添加边使得这棵树双联通。

    定理：添加的边数为ceil（叶子节点数/2) = trunc((叶子节点数+1)/2)

  #include <iostream>
  #include <cstring>
  #include <algorithm>
  #include <vector>
  #include <stack>
  using namespace std;
  
  const int maxv = 1005;
  const int maxe = 1005;
  
  struct edge {
    int f, t;
    edge() {}
    edge(int u, int v) :f(u), t(v) {}
  };
  
  vector<edge> edges;
  vector<int> G[maxv];
  
  // directed
  void insert_edge(int a, int b) {
    edges.push_back(edge(a, b));
    int s = edges.size() - 1;
    G[a].push_back(s);
  }
  
  int dfn[maxv], low[maxv], vis[maxv], parent[maxv], deg[maxv];
  int idx, N, M, ncolor;
  
  void init() {
    idx = 0;
    ncolor = 0;
    memset(vis, 0, sizeof(vis));
    memset(deg, 0, sizeof(deg));
    memset(parent, 0, sizeof(parent));
    edges.clear();
    for (int i = 0; i < maxv; i++) G[i].clear();
  }
  
  // naive undirected tarjan
  void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    vis[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = edges[G[u][i]].t;
        if (!vis[v]) {
            parent[v] = u;
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (parent[u] != v) {
            low[u] = min(low[u], low[v]);
        }
    }
  }
  
  int solve() {
      // sanity check for unconnection. 
    for (int u = 1; u <= N; u++) if (!vis[u]) tarjan(u);
      // check all edges
    for (int u = 1; u <= N; u++) {
        for (int i = 0; i < G[u].size(); i++) {
            int v = edges[G[u][i]].t;
              // bridge， only add low[u], since there are 2 edges between u&v.
            if (low[u] != low[v]) deg[low[u]]++;
        }
    }
    int cnt = 0;
      // count leaves
    for (int c = 1; c <= N; c++)
        if (deg[c] == 1) cnt++;
    return (cnt + 1) / 2;
  }
  
  int main() {
    while (cin >> N >> M && N && M) {
        init();
        int a, b;
        for (int i = 0; i < M; i++) {
            cin >> a >> b;
            insert_edge(a, b);
            insert_edge(b, a);
        }
        cout << solve() << endl;
    }
  }
  

  • SPF

  点双连通分量，也不用显式的染色，只需要数每个割点的边的出点的low[]的种类数即可。

  #include <iostream>
  #include <cstring>
  #include <algorithm>
  #include <vector>
  #include <queue>
  #include <stack>
  #include <set>
  using namespace std;
  
  const int maxv = 1005;
  const int maxe = 10005;
  const int maxw = 0x7fffffff;
  
  struct edge {
    int f, t, w;
    edge() {}
    edge(int u, int v, int w) :f(u), t(v), w(w) {}
  };
  
  vector<edge> edges;
  vector<int> G[maxv];
  
  // directed
  void insert_edge(int a, int b, int c=0) {
    edges.push_back(edge(a, b, c));
    int s = edges.size() - 1;
    G[a].push_back(s);
  }
  
  int vis[maxv], dfn[maxv], low[maxv], iscut[maxv], parent[maxv];
  
  int a, b, idx, N, nrs;
  
  void init() {
    for (int i = 0; i < maxv; i++) G[i].clear();
    edges.clear();
    memset(vis, 0, sizeof(vis));
    memset(iscut, 0, sizeof(iscut));
    memset(parent, -1, sizeof(parent));
    idx = 0;
    N = 0;
    nrs = 0;
  }
  
  stack<int> stk;
  void tarjan(int u) {
    dfn[u] = low[u] = idx++;
    vis[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = edges[G[u][i]].t;
        if(!vis[v]) {
            parent[v] = u;
            if (u == 1) nrs++;
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (dfn[u] <= low[v]) {
                iscut[u] = 1;
            }
        }
        else if (parent[u] != v) {
            low[u] = min(low[u], dfn[v]);
            //low[u] = min(low[u], low[v]);
        }
    }
    if (u == 1 && nrs < 2) iscut[u] = 0;
  }
  
  int main() {
    int cas = 1;
    while (cin >> a && a) {
        init();
        if (cas != 1) cout << endl;
        cout << "Network #" << cas++ << endl;
        cin >> b;
        insert_edge(a, b);
        insert_edge(b, a);
        N = max(max(a, b), N);
        while (cin >> a && a) {
            cin >> b;
            insert_edge(a, b);
            insert_edge(b, a);
            N = max(max(a, b), N);
        }
        // assume: graph is connected
        tarjan(1);
        bool flag = false;
        set<int> cnt;
        for (int i = 1; i <= N; i++) {
            if (iscut[i]) {
                flag = true;
                cnt.clear();
                for (int j = 0; j < G[i].size(); j++) 
                    cnt.insert(low[edges[G[i][j]].t]);
                cout << "  SPF node " << i << " leaves " << cnt.size() << " subnets" << endl;
            }
        }
        if (!flag) cout << "  No SPF nodes" << endl;
    }
  }