DFS的应用

1. 求无向图的连通分量

bool vis[maxn];

void DFS(int u){
    for(int i = 0;i < G[u].size(); ++i){
        if(!vis[G[u][i]]){
            vis[G[u][i]] = 1;
            dfs(G[u][i]);
        }
    }
}

int Count(int n){
    int num = 0;
    for(int i = 0;i < n; ++i){
        if(!vis[i]) vis[i] = 1,num++,DFS(i);
    }
    return num;
}

求无向图的割点和桥

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];
        if(!pre[v]){
            child++;
            int lowv = dfs(v,u);
            lowu = min(lowu,lowv);
            if(lowv >= pre[u]){
                iscut[u]++;
            }
        }
        else if(pre[v] < pre[u] && v != fa){
            lowu = min(lowu,pre[v]);
        }
    }
    if(fa < 0&&child == 1) iscut[u] = 0;
    else if(fa < 0&&child >= 2) iscut[u] = child-1;
    return low[u] = lowu;
}

2. 求无向图的双连通分量

双连通的tarjan 算法

/ 无向图的点联通分量

const int maxn= 1000+10;
int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;
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]){
      S.push(e);
      child++;
      int lowv = dfs(v,u);
      lowu = min(lowu,lowv);
      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(pre[v],lowu);
    }
  }
  if(fa < 0&& child == 1) iscut[u] = 0;
  return lowu;
}
void find_bcc(int n){
  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);

}

//无向图的边-双联通分量
// 第一边dfs求出所有的割边，然后第二边dfs求出所有边—双连通分量（不经过割边）

3. 求有向图的强连通分量


// tarjan算法
const int maxn = 2e4+100;

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;
    me(sccno),me(pre);
    rep(i,0,n) if(!pre[i]) dfs(i);
}
// kosaraju



const int maxn = 2e4+100;
vector<int> G[maxn],G2[maxn];
vector<int> S;
int vis[maxn],sccno[maxn],scc_cnt;
void dfs1(int u){
    if(vis[u]) return ;
    vis[u] = 1;
    for(int i = 0;i < G[u].size(); ++i) dfs1(G[u][i]);
    S.push_back(u);
}
void dfs2(int u){
    if(sccno[u]) return  ;
    sccno[u] = scc_cnt;
    for(int i = 0;i < G2[u].size(); ++i) dfs2(G2[u][i]);
}
void find_scc(int n){
    scc_cnt = 0;
    S.clear();
    memset(sccno,0,sizeof(sccno));
    memset(vis,0,sizeof(vis));
    for(int i = 0;i < n; ++i) dfs1(i);
    for(int i = n-1;i >= 0;--i){
        if(!sccno[S[i]]) {
            scc_cnt++;
            dfs2(S[i]);
        }
    }
}

4. 拓扑排序


const int maxn = 1e5+100;
bool vis[maxn];
stack<int> S;
vector<int> G[maxn];
void dfs(int u){
    for(int i  = 0;i < G[u].size(); ++i){
        if(!vis[G[u][i]]){
            vis[G[u][i]];
            dfs(G[u][i]);
        }
    }
}
void Topo(int n){
    memset(vis,0,sizeof(vis));
    for(int i = 0;i < n; ++i) {
        if(!vis[i]){
            vis[i] = 1;
            dfs(i);
        }
    }
    // 然后令S出栈，出栈顺序即为拓扑序
}

5. 二分图判断

bool bipartite(int u,int b){
  for(int i = 0;i < G[u].size(); ++i){
    int v = G[u][i]; if(bccno[v] != b) continue;
    if(color[v] == color[u]) return false;
    if(!color[v]){
      color[v] = 3-color[u];
      if(!bipartite(v,b)) return false;
    }
  }
  return true;
}

`