图论(1)

Tarjan

Tarjan算法是一种非常实用的图论算法，可以解决连通块、割点、缩点、桥等问题。

建图

建图采用链式前向星方式。

int head[maxn];  //表头
int nxt[maxn];   //链表下一位
int edge[maxn];  //该边终点
int weight[maxn];  //该边的权值
int tot;   //边的数量
void addEdge(int u,int v,int w)
{
    edge[++tot] = v;
    weight[tot] = w;
    nxt[tot] = head[u];
    head[u] = tot;
}
//遍历方式
void traverse()
{
    for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=nxt[j])
            cout<<i<<" "<<edge[j]<<endl;
}

强连通分量

强连通分量，即图的一个子集。如果两个顶点可以相互通达，则称这两个点强连通(strongly connected).如果有向图的每两个顶点都强连通，则称图G为强连通图。有向图的强连通子图，称为强连通分量。

弄懂Tarjan算法需要明白最重要的两个数组：$dfn、low$​​.

$dfn[x]$​​记录每个点最早被遍历的时间，即在dfs过程中$x$的时间戳。

$low[x]$​​​表示从$x$​​处搜索，能够回溯到的最早被遍历的点的时间戳。

用$vis$数组来记录每个点的分块编号，或者换个写法表示每个点所在的连通块的根的编号也可。

使用dfs遍历图，每次访问到新节点$u$​时，向栈中压入$u$​，记录$dfn[u]==low[u]$​，并依次访问该节点的每一个相邻节点$v$​.会出现三种情况：

1. $dfn[v]==0$:此时$v$​​还没有搜索到，直接对$v$​进行递归，会得到$low[v]$​,故更新$low[u] = min(low[u],low[v])$​​
2. $vis[v]==0$:此时$v$​早在$u$​之前就已经访问过了，但是$u$​的邻接点还未遍历完全，更新$low[u]=min(low[u],dfn[v])$​.
3. $vis[v]!=0$:此时$v$已经操作完全，略过。

对于第二种情况的$v$​，我们用其$dfn$值更新$u$的$low$值的原因是，从$u$处能搜到曾经搜过的$v$，那么从$v$开始就有可能存在一个强联通块包含了$u$，因此我们将$u$的low值更新，再通过回溯时对low值的更新，一步步更新回$v$点，若$low[v]$与$dfn[v]$相等，就说明从$v$开始绕了一圈又找到了$v$，也就是说找到了强连通分量。
那么如何对应地找到其中所有的节点呢？我们通过栈来实现，在dfs过程中，若遇到没搜过的点，则将其入栈，最后在$low[u]=dfn[u]$处，因为从$u$处最终能走回$u$，回溯到$u$​时，途中的所有节点都在栈中，而中途可能遇到的分支都会在相同的过程中全部出栈（不在环中的自成一个强连通分量），因此从栈顶到栈中$u$的位置，中间的节点正好在一个强连通分量中，所以我们只需要不断弹栈，直到将$u$弹出栈，所有弹出的元素都归为一个强联通块中。可以证明，这样求得的强联通块是最大强联通块，将强联通块抽象成点，这便是缩点

void Tarjan(int u)
{
    dfn[u] = low[u] = ++tit;  //时间戳
    st.push(u);
    for(int i=head[u];i;i=nxt[i])
    {
        int v = edge[i];
        if(!dfn[v]){
            Tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(!vis[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        vis[u] = ++cnt;   //连通块编号
        while(st.top()!=u)
        {
            vis[st.top()] = cnt;  //栈顶到u的一块都在一个连通块中
            st.pop();
        }
        st.pop();
    }
}

上题目校园网 缩点

割点

割点是指若将连通图的某个点及其连接的边删去后，图中的连通分量增加，则称这个点为割点。

对于点$u$，假如其从$fa$搜索而来，连接着某点$v$,若$low[v] \geq dfn[u]$,则$u$​是割点。

可以画出图来理解，如果我们将$u$和其连接的边删掉，$v$和$fa$必然不属于同一个连通块。若删掉后$v$和$fa$属于同一个连通块，那么$low[v]$必然会小于$dfn[u]$。通过这一点我们可以对每个走过的点都用其$dfn$值更新$u$的$low$值，就是为了保证求出的割点一定保证$fa$和$v$不在任何同一个连通块中。

那么这时我们会考虑一个特殊的点：第一个被搜索的点，这个点没有$fa$。该如何确定这个点是不是割点呢？我们直接记录其子树数量，如果其子树数量大于1，那么就是割点，因为把它去掉，其子树不能相互到达。

于是算法模板如下

void tarjan(int u,int root)
{
    dfn[u] = low[u] = ++tit;
    int childtree = 0;  //根的子树数量
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v = e[i].to;
        if(!dfn[v]){
            tarjan(v,root);
            low[u] = min(low[u],low[v]);
            if(low[v]>=dfn[u]&&u!=root){
                cut[u] = true;   //记录u节点为割点
            }
            if(u==root)
                childtree++;
        }
        else
            low[u] = min(low[u],dfn[v]);
    }
    if(childtree>=2&&u==root)
        cut[u] = true;    // 根节点也为割点
}

根据上述求法，我们还可以统计出删掉割点$u$之后连通块增加的个数

对于第一个搜索的点，连通块增加的个数是$childtree-1$。

对于其他点，连通块增加的个数是$u$被判为割点的次数

if(low[v]>=dfn[u]&&u!=root)
    cut[u] = true;
改为
if(low[v]>=dfn[u]&&u!=root)
    ++delta[u];   //删去u增加的连通图数量
if(childtree>=2&&u==root)
	cut[u] = true; 
改为
if(childtree>=2&&u==root)
    delta[root] = childtree-1;

上例题 割点 嗅探器

桥

在无向图中，删去一条边，使得图的连通块数量增加，则称这条边为桥。

在$tarjan$​的过程中，若$u$连接着$v$,$low[v]>dfn[u]$,则连接$u、v$的边是桥，可画图理解。

void Tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++cnt;
    //桥在无向图中是两条相同的边，所以边一般从0开始编号
    for (int i = head[u]; i != -1; i = nxt[i])  
    {
        int v = edge[i];
        if (dfn[v] == 0)
        {
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
                bridge[i] = bridge[i ^ 1] = true;//i和i^1这两条边是同一条边，是桥
        }
        else if (fa != v)
            low[u] = min(low[u], dfn[v]);
    }
}

上例题 炸铁路

拓扑排序

在图论中，拓扑排序(Topological Sorting)是一个有向无环图(DAG,Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足以下两个条件：

1. 每个顶点出现且仅出现一次。
2. 若存在一条从顶点A到顶点B的路径，则在序列中顶点A在顶点B的前面出现。

有向无环图(DAG)才有拓扑排序，非DAG图没有拓扑排序一说。根据定义可知，一个DAG图的拓扑排序也许不止一个。

直接上题 摄像头

#include<iostream>
#include<queue>

using namespace std;
const int maxn = 510;
int edge[maxn],head[maxn],nxt[maxn];
int ind[maxn],outd[maxn];
int has[maxn],a[maxn];
int n,tot,ans;
queue<int> q;

void addEdge(int u,int v)
{
    edge[++tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int m,y;
        cin>>a[i]>>m;
        has[a[i]] = 1;  //该位置被监视
        while(m--)
        {
            cin>>y;
            addEdge(a[i],y);
            outd[a[i]]++,ind[y]++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(ind[a[i]]==0)
            q.push(a[i]);
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(has[u]) ans++;  //砸掉摄像头，该位置不被监视
        for(int i=head[u];i;i=nxt[i])
        {
            int v=edge[i];
            ind[v]--;
            if(ind[v]==0&&has[v]==1)
                q.push(v);
        }
    }
    if(ans==n)
        cout<<"YES"<<endl;
    else
        cout<<n-ans<<endl;
    return 0;
}
	

旅行计划