学习笔记2（图的连通性）

图的遍历

方法一：宽搜

queue<int> q;
void bfs(int s){
    q.push(s);
    mark[s]=1;
    while(q.size()){
        int x=q.front();
        q.pop();
        cout<<x<<endl;
        for(int i=Last[x];i;i=Next[i]){
            int y=End[i];
            if(!mark[y]){
                q.push(y);
                mark[y]=1;
            }
        }
    }
}

方法二：前序遍历

void dfs(int x){
    cout<<x<<endl;
    mark[x]=1;
    for(int i=Last[x];i;i=Next[i]){
        int y=End[i];
        if(!mark[y])
            dfs(y);
    }
}

方法三：后序遍历

void dfs(int x){
    mark[x]=1;
    for(int i=Last[x];i;i=Next[i]){
        int y=End[i];
        if(!mark[y])
            dfs(y);
    }
    cout<<x<<endl;
}

PS：为了节约篇幅，以下代码全部是暴力存图，请换成更优化的存图方式！！！

连通图

在无向图中，任意两点都直接联通或间接联通。

子图

表示在一个图中删去若干条边或删去若干点得到的新的图就是它本身的子图（说白了就是一个图的一部分）

PS：一个图的子图包括它本身

如果一个图的子图是连通图，则称这个子图为联通子图

连通分量

无向图G的最大联通子图成为G的连通分量。

最大连通子图的含义：

该子图是G的连通子图，将G的任何不在该子图中的了点加入到该子图后，该子图将不再连通。

有向图的连通性

在有向图中，对于每一对定点Vi,Vj都存在从Vi到Vj和从Vj到Vi的路径（任意两点之间都存在可到达对方的路径），则称改图为强连通图。

如果有向图G的子图是连通图，则称这个子图为强连通子图

有向图G的最大强连通分量称为G的强连通分量。

最大强连通分量的含义：

该子图是G的强连通子图，将G的任何不在该子图中的点加入到该子图后，该子图不再连通。

求强连通分量（Kosaraju算法）

在图G中找一个未被讨论的点，从它开始DFS后序遍历图G，遍历到的点都置为已讨论，用vis数组记录每个点遍历的先后次序。
重复执行1，直到所有节点被讨论。
将G’变成原图的一个反图，用DFS遍历一遍，每次找到一个新的起点，就找到了一个强连通分量。## 求强连通分量（Kosaraju算法）

为什么遍历一次G的反图就可以求出强连通分量？

因为强连通分量你不管怎么反过来，始终还是强连通分量

为什么第一次DFS要后序遍历？

因为没法保证在一个队列和数组中强连通分量在一块，且有些去不了的点,用前序就会弄错

代码：

const int N=105;
//map1记录正向图，map2记录反向图，pos记录进入vis数组的店的个数，scc记录强连通分量的个数
int vis[N],n,m,pos,scc;                //vis记录n个点的遍历次序 
bool mark[N],map1[N][N],map2[N][N]; //mark记录该店是否被遍历过
void dfs1(int s){//正向深搜 
    mark[s]=true;
    for(int i=1;i<=n;i++)
        if(map1[s][i] && !mark[i])
            dfs1(i);
    pos++;//后序遍历 
    vis[pos]=s;
}
void dfs2(int s){//反向深搜 
    mark[s]=true;
    for(int i=1;i<=n;i++)
        if(map2[s][i] && !mark[i])
            dfs2(i);    
}
void Kosaraju(){//Kosaraju算法
    //dfs1正向深搜 
    for(int i=1;i<=n;i++)
        mark[i]=false;
    for(int i=1;i<=n;i++)
        if(!mark[i])
            dfs1(i);
    //dfs2反向深搜 
    for(int i=1;i<=n;i++)
        mark[i]=false;
    for(int i=n;i>=1;i--)//每深搜完一次，表示找到一个强连通分图，增加scc 
        if(!mark[vis[i]]){
            dfs2(vis[i]);
            scc++;    
        }
    printf("%d",scc);
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        map1[x][y]=map2[y][x]=true;
    }
}
int main(){ 
    init();
    Kosaraju();
    return 0; 
}

有向图的压缩（缩点）

强连通分量缩点代码：

void dfs1(int s){//正向深搜 
    mark[s]=true;
    for(int i=1;i<=n;i++)
        if(map1[s][i] && !mark[i])
            dfs1(i);
    pos++;//后序遍历
    vis[pos]=s;
}
void dfs2(int s){//反向深搜 
    mark[s]=true;
   belong[s]=scc;
    for(int i=1;i<=n;i++)
        if(map2[s][i] && !mark[i])
            dfs2(i);
}
void Kosaraju(){
    //dfs1正向深搜 
    for(int i=1;i<=n;i++)
        mark[i]=false;
    for(int i=1;i<=n;i++)
        if(!mark[i])
            dfs1(i);
    //dfs2反向深搜 
    for(int i=1;i<=n;i++)
        mark[i]=false;
    for(int i=pos;i>=1;i--)
        if(!mark[vis[i]]){
            dfs2(vis[i]);
            scc++;    
        }
    //合为一点
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if((belong[i]!=belong[j])&&(map1[i][j]))//belong[i]表示i号点的强连通分量
                ru[belong[j]]=true;
    for(int i=1;i<=scc;i++)
        if(!ru[i])
            tot++;
    printf("%d",tot); 
}

求强连通分量（Tarjan算法）

算法思想：

做一遍DFS，用dfn[i]表示编号为i的节点在DFS过程中的访问序号(也可以叫做开始时间）用low[i]表示i节点及其下方节点所能到达的开始时间最早的节点的开始时间。初始时dfn[i]=low[i]
在DFS过程中会形成一搜索树。在搜索树上越上层的节点，显然dfn的值就越小。
如果发现某节点有边连到搜索树中自己的祖先节点，则更新其low值。

如果一个节点的low值等于dfn值，则说明其下方的节点不能走到其上方的节点，那么该节点u就是一个强连通分量在DFS搜索树中的根。

但是u的子孙节点未必就和u处于同一个强连通分量（比如图中b和c），怎样找出u的子孙中，哪些跟它位于同一强连通分量？

用栈解决！！！

Tarjan算法代码：（时间复杂度O（n+m））

stack<int> S;
void Tarjan(int u){//当前讨论到u号节点 
    dfn[u]=low[u]=++visittime;
    S.push(u);
    instack[u]=true;//instack[v]用于标记v是否在栈中 
    for(int v=1;v<=n;v++){
        if(map[u][v] && !dfn[u]){//dfn[v]==0表示v号点没有被访问过 
            Tarjan(v);//v是u的儿子节点，继续深搜 
            low[u]=min(low[u],low[v]);    
        }
        else if(map[u][v] && dfn[v] && instack[v])//v比u先被访问，u不是v的父亲，<u,v>是条返祖边 
            low[u]=min(low[u],dfn[v]);
        if(dfn[u]==low[u]){//u是强连通分量的根 
            scc++;//scc用于统计强连通分量的个数 
            do{
                v=S.top()
                S.pop();
                belong[v]=scc;//记录下i号点属于哪个强连通分量 
                instack[v]=false;
            }while(u!=v);
            //退栈，把整个强连通分量都弹出来 
        }
    }
}

Tarjan算法缩点代码:（消息的传递）

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int Map[N][N],n;
int low[N],dfn[N],Belong[N],cnt,scc;
bool InStack[N],ru[N];
stack<int> S;
void Tarjan(int u){
    dfn[u]=low[u]=++cnt;
    S.push(u);
    InStack[u]=true;
    for(int v=1;v<=n;v++){
        if(Map[u][v] && !dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(Map[u][v] && dfn[v] && InStack[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        scc++;
        int v;
        do{
            v=S.top();
            S.pop();
            Belong[v]=scc;
            InStack[v]=false;
        }while(u!=v);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&Map[i][j]);
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            Tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(Belong[i]!=Belong[j] && Map[i][j])
                ru[Belong[j]]=true;
    int tot=0;
    for(int i=1;i<=scc;i++)
        if(!ru[i])
            tot++;
    printf("%d",tot);
}

Tarjan链式前项星代码：

stack<int> S;
void Tarjan(int u){
    dfn[u]=low[u]=++cnt;
    S.push(u);
    InStack[u]=true;
    for(int i=Last[u];i;i=Next[i]){
        int v=End[i];
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(dfn[v] && InStack[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        scc++;
        int v,k=0;
        do{
            k++;
            v=S.top();
            S.pop();
            Belong[v]=scc;
            InStack[v]=false;
        }while(u!=v);
        a[scc]=k;
    }
}
void cb(int x,int y){
    End[++tot]=y;
    Next[tot]=Last[x];
    Last[x]=tot;
}
int main(){
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            Tarjan(i);
    for(int i=1;i<=n;i++)
        for(int j=Last[i];j;j=Next[j]){
            int v=End[j];
            if(Belong[i]!=Belong[v])
                c[Belong[i]]=true;
        }
}