Day10 图论-3

常规
1

组员：盛赞宇、陈隆铭、王浩宇、付骞煜、丁文淏

拓扑排序

  • 步骤
    在有向无环图(DAG)中
    1.统计所有点的入度
    2.将所有入度为0的点入队
    3.while出队,当前将点连接到的点入度-1
    4.如果连接到的点入度为0就入队

    示范：

    for(int i=0;i<n;i++){
    if(in[i]==0)
        q.push(i);
}
while(!q.empty()){
    int u=q.front();q.pop();
    for(int v=/*从点i出发的所有边*/){
        in[v]--;
        if(in[v]==0)
            q.push(v);
    }
}
    • tips:
      1.判断拓扑序列是否唯一：q.front()>1
      2.求字典序最小的拓扑序列：使用优先队列

  • 求有向无环图(DAG)最长路
    定义f[i]为以i为结尾的最长路长度

    while(!q.empty()){
    int u=q.front();q.pop();
    for(int i=/*从u出发的边*/){
        f[v]=max(f[v],f[u]+w[i]);
    }
}
    • 求DAG路径数：f[i]=∑[i的前驱]

Tarjan

  • 定义

    • dfn[u]：节点u的dfs序
    • low[u]：u或其的子树的节点，经过最多一点返祖边能够追溯到dfn最小的节点
    • 连通分量：无向图的连通块
    • 强连通分量：有向图的双向可达连通块

  • 步骤
    1.从任意一点出发遍历一张有向图
    2.标记每个节点，每个节点仅访问一次
    3.只保留所有搜索递归回溯的边，得到一棵生成树

    示范：

    void tarjan(int x){
    dfn[x]=low[x]=++top;
    book[x]=true;
    stk.push(x);
    for(int i=head[x];i!=-1;i=a[i].next){
        if(dfn[a[i].to]){
            tarjan(a[i].to);
            low[x]=min(low[x],low[a[i].to]);
        }
        else if(book[a[i].to]){//这是一条返祖/横向边
            low[x]=min(low[x],dfn[a[i].to]);
        }
    }
}
    • 记f[i]走到i的最大权值和：f[i]=max(f[前驱]+w)

  • 割点

    • 定义
      若去掉x及其相邻所有的边，会破坏图的连通性，则x为割点
    • 判断
      1.若x为树根，且存在多个子节点，则x为割点
      2.若dfn[x]<=low[y],则x为割点

  • 割边(桥)

    • 定义
      1.无向图中的一条边，删掉会不连通
      2.若不存在割边，边双连通图
    • 判断
      dfn[x]<low[y]