2021.07.16笔记-图论字符串1

2021/7/18 23:12:32

编程Tag： 字符串 int 节点匹配图论 16 fail nxt 2021.07

本文主要是介绍2021.07.16笔记-图论字符串1，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

写在前面

讲师： \(Zhang\_RQ\)

内容：图论（上午）： \(Tarjan\) 差分约束欧拉回路二分图；字符串（下午）：哈希，\(KMP\) ，\(Trie\) 树，\(AC\) 自动机，\(Manacher\)

笔记 \(by \ DReamLion\) ，部分代码来自 @\(wsy\_jim\) ，\(AC\) 自动机部分由 @\(wsy\_jim\) 执笔，特此鸣谢

wsy_jim's blog

图论

Tarjan

有向图Tarjan

不是今天讲的，具体内容见寒假的课件

找强连通分量

int m,e[N],ne[N],h[N],idx,n,dfn[N],low[N],num;
int sta[N],top;
int bel[N],sum[N],res=0;

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

inline int read(){
    int x=0,y=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*y;
}

void tarjan(int x){
    dfn[x]=low[x]=++num;
    sta[++top]=x;
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j);
            low[x]=min(low[x],low[j]);
        }else if(!bel[j]) low[x]=min(low[x],dfn[j]);
    }
    if(low[x]==dfn[x]){
        bel[x]=++res;
        ++sum[res];
        while(sta[top]!=x){
            ++sum[res];
            bel[sta[top]]=res;
            --top;
        }
        --top;
    }
}

int main(){

    memset(h,-1,sizeof h);

    n=read(),m=read();

    for(int i=1;i<=m;i++){
        int a,b;
        a=read(),b=read();
        add(a,b);
    }

	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
    
    for(int i=1;i<=res;i++){
        for(int j=1;j<=n;j++){
            if(bel[j]==i) printf("%d ",j);
        }
        printf("\n");
    }
    return 0;
}

无向图Tarjan

概念

割点：对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）

割边：对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为割边（又称桥）

一些等价的性质

（设 \(v\) 是连通图 \(G\) 的节点， \(e\) 是连通图 \(G\) 的一条边）

\(v\) 是 \(G\) 的一个割点 = 存在与 \(v\) 不同的两个节点 \(u\) 和 \(w\) ，使得任意一条 \(u\) 到 \(w\) 的道路 \(P_{uw}\) 都经过 \(v\) = \(V-v\) 可划分为两个节点集 \(U\) 和 \(W\) ，使得对任意节点 \(u\in U\) 和 \(w\in W\) ，节点 \(v\) 都在每一条道路 \(P_{uw}\) 上
\(e\) 是 \(G\) 的一条割边 = \(e\) 不属于 \(G\) 的任何回路 = 存在 \(G\) 的节点 \(u\) 和 \(w\) ，使得 \(e\) 属于 \(u\) 和 \(w\) 的任何一条道路 \(P_{uw}\) = \(G-e\) 可以划分为两个节点集 \(U\) 和 \(W\) ，使得对任何节点 \(u\in U\) 和 \(w\in W\) ，在 \(G\) 中道路 \(P_{uw}\) 都经过 \(e\)

算法

\(Tarjan\) 基于在无向图上的 \(dfs\)

\(dfn_x\) ：\(dfs\) 时的时间戳，即 \(dfs\) 中第一次搜索到 \(x\) 的次序

\(low_x\) ：\(x\) 经过至多一条非树边能访问到的所有节点中最小的 \(dfn\) ，即在以 \(x\) 为根的子树内的点通过一条非树边到达的 \(dfn\) 最小的节点 \(y\) 的 \(dfn\) 值，\(y\) 能到达 \(x\)

\(low\) 的更新方法：\((u,v)\) 有边。若 \(v\) 是 \(v\) 在 \(dfs\) 树上的孩子，则有 \(low_u=min(low_u,low_v)\) ，否则 \(low_u=min(low_u,dfn_v)\)

选定一个根节点，从该点开始 \(dfs\) ，遍历整张图

对于根节点，若它有两棵及以上的子树，则它是割点。因为若去掉这个点，它的子树之间不能互相到达

对于非根节点 \(u\) ，若存在 \(u\) 的孩子 \(v\) ，有 \(dfn_u\le low_v\) ，说明 \(v\) 无法到达 \(u\) 的祖先，即 \(u\) 是割点。因为从 \(v\) 到以 \(u\) 为根的子树外的点都必须经过点 \(u\)

对于点 \(u\) 和 \(u\) 的孩子 \(v\) ，若存在边 \((x,y)\) ，有 \(dfn_u<low_v\) ，则边 \((x,y)\) 是割边，因为以 \(v\) 为根的子树内的点都必须经过该边

找点双连通分量

int e[N],ne[N],h[N],idx=2;
int n,m,dfn[N],low[N];
int sta[N],top=0;
int son=0,res=0;
set<int> s[N];
bool cut[N];//是否是割点

inline int read(){
    int x=0,y=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*y;
}

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int x,int fa){
    dfn[x]=low[x]=++idx;
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        if(!dfn[j]){
            sta[++top]=i;
            tarjan(j,x);
            son++;
            low[x]=min(low[x],low[j]);
            if(low[j]>=dfn[x]){
                res++;cut[x]=1;
                while(sta[top]!=i){
                    s[res].insert(e[sta[top]]);
                    s[res].insert(e[sta[top]^1]);
                    --top;
                }
                s[res].insert(x),s[res].insert(j);
                --top;
            }
        }else low[x]=min(low[x],dfn[j]);
    }
    if(fa==0&&son==1) cut[x]=0;
}

int main(){

    memset(h,-1,sizeof h);

    n=read(),m=read();

    for(int i=1;i<=m;i++){
        int a,b;
        a=read(),b=read();
        add(a,b);
        add(b,a);
    }

    tarjan(1,0);

    for(int i=1;i<=res;i++){
        for(set<int>::iterator j=s[i].begin();j!=s[i].end();j++){
            printf("%d ",*j);
        }
        printf("\n");
    } 
    
    return 0;
}

找边双连通分量

int e[4*N],ne[4*N],h[N],idx;
int n,m,dfn[N],low[N],res=0,top=0,sta[N],num=0;
int bel[N],sum[N];
bool cut[4*N];

inline int read(){
    int x=0,y=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*y;
}

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int x,int fa){
    dfn[x]=low[x]=++num;
    sta[++top]=x;
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        if(!dfn[j]){
            tarjan(j,x);
            low[x]=min(low[x],low[j]);
            if(low[j]>dfn[x]){
                res++;
                cut[i]=1;
                bel[j]=res;
                while(sta[top]!=j){
                    sum[res]++;
                    bel[sta[top]]=res;
                    top--;
                }
                top--;
            }
        }else low[x]=min(low[x],dfn[j]);
    }
}

int main(){

    memset(h,-1,sizeof h);

    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int a,b;
        a=read(),b=read();
        add(a,b);
        add(b,a);
    }

    tarjan(1,0);

    for(int i=0;i<=res;i++){
        for(int j=1;j<=n;j++){
            if(bel[j]==i) printf("%d ",j);
        }
        printf("\n");
    }
    return 0;
}

例题

[HDU 4738] Caocao's Bridges

Caocao's Bridges

给出一个由\(n\)个点和\(m\)条边构成的无向图，表示\(n\)个岛屿之间的\(m\)条道路，现在周瑜有一个炸.药，可以炸掉任意的一条道路，不过每条道路都有一个权值，代表这条道路上防守的卫兵数量，如果周瑜想要炸掉这条道路就必须带上不少于这条路权值的士兵才行，现在问能否带上尽量少的士兵去炸掉一条道路，使得整张无向图变为不相连的两部分。 \(n\le 1000,T\le 12\)

板子题求最小割边

坑点：①特判图是不连通的 ②如果一个割边的权值是 \(0\) ，那么答案也是 \(1\) ③可能会有重边
[POJ 2117] Electricity

Electricity

给定一张无向图，求任意删掉一个点能得到的最大联通分量数。 \(n\le 10^4\)

只有删割点的时候连通分量数才会增加

删掉一个割点时增加的连通分量数就是满足 \(low_v\ge dfn_u\) 的 \(v\) 的个数（对于根节点要 \(-1\) ，因为没有祖先那一侧的连通块了）
[POJ 1523]

SPF

给定一个连通网络，网络的结点数\(<=1000\)，求出这个网络的所有割点编号，并求出若删去其中一个割点\(k\)后，对应的，原网络会被分割为多少个连通分量？

类似例题2，具体过程这里不写了
[Network]

Network

给定一张无向图，有若干次询问，每次询问时添加一条边，问图中还剩多少条割边。 \(n\le 10^5,q\le 1000\)

添加边 \((u,v)\) 会使路径 \((u,v)\) 上的边不能是割边（添加一条非树边会构成一个环，环上的边就不是割边了）

各条非树边之间互不影响

找生成树跑 \(tarjan\)

割边计数，去掉路径上的割边数量即为答案

边上答案下放到点上

树上差分

差分约束

算法

判断差分约束系统是否有解

给定一个 \(n\) 元的不等式组，判断其是否有解

每个不等式组形如 \(x_i-x_j\le c_k\)

不等式变形后为 \(x_i\le x_j+c_k\) ，类似最短路的松弛操作。因此从 \(j\) 点向 \(i\) 点连一条长度为 \(c_k\) 的有向边以表示这个约束

最后加一个虚拟的 \(0\) 号点并向所有点加一边权为 \(0\) 的有向边，跑以 \(0\) 号点为源点的单源最短路，如果有负环则无解，否则有解则某一组解为每个点的距离

判是否有负环用 \(Bellman\_ford\) 或 \(SPFA\) ，因为有负边所以不能用 \(dijkstra\)

复杂度 \(O(nm)\)

例题

[Luogu P1993] 小 k 的农场

P1993 小 K 的农场

板子题
[Luogu P4926] [1007] 倍杀者

P4926 [1007]倍杀测量者

给定 \(x_{a_i} \ge (k_i-t)\times x_{b_i} ，(k_i+t)\times x_{a_i}>x_{b_i}\)，求最大的 \(t\) 使得不等式无解

二分答案

取 \(log\) 以后变成差分约束问题

*注意取 \(log\) 的操作！因为 \(log(ab)=log(a)+log(b)\) ，所以通过取 \(log\) 把乘法变成加法，类似P2384 ~~其实不取也能过，因为乘积也不大~~
- 连边
\[x_{a_i}\ge (k_i-t)\times x_{b_i} \\ log_2(x_{a_i})\ge log_2(x_{b_i})+log_2(k_i)-t \]
add(b,a,log2(k-t))

\[(k_i+t)\times x_{a_i}>x_{b_i} \\ log_2(x_{a_i})+log_2(k_i+t)>log_2(x_{b_i}) \\ log_2(x_{a_i})>log_2(x_{b_i})-log_2(k_i+t) \]
add(b,a,-log2(k+t))
- 仅当 \(t=0\) 时，不等式仍然有解，即不存在，输出 \(-1\)
- 查 \(t\) 具体是多少用二分答案

欧拉图

概念

定义：存在欧拉回路的图即欧拉图 ~~这不废话吗~~

欧拉回路：经过所有边恰好一次的图

奇点/偶点：度数为奇数/偶数的点

判定

对于无向图，连通且所有点都是偶点

对于有向图，所有点都在一个强连通分量中且每个点出度和入度相等

Hierholzer算法

选择任一顶点为起点，遍历所有相邻边

深搜，访问相邻顶点，每次删经过的边

若顶点无相邻边就将顶点入栈

栈中顶点倒序输出，就是从起点出发的欧拉回路

void dfs(int x){
  for(int y=1;y<=n;y++){
    if(mp[x][y]>0){
      mp[x][y]--;
      mp[y][x]--;
      dfs(y);
    }
  }
  s[tmp--]=x;
}

例题

[The Necklace]

UVA10054 The Necklace

将每种颜色看做一个点，每个珠子的两种颜色就是在这两种颜色之间连边，跑欧拉回路（跑遍所有边=用尽所有珠子）

二分图

概念

定义：若一个无向图满足可以将点集分为两部分且两部分点集之间无连边，则为二分图

性质：二分图只有偶环，没有奇环 ~~证明就感性理解一下吧~~

匹配：一个边的子集且所有点至多出现一次

最大匹配：边最多的匹配（最大匹配可转换为网络流问题）

判定

黑白染色

int n;// n表示点数
int h[N], e[M], ne[M], idx;// 邻接表存储图
int color[N];// 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c){
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if (color[j] == -1){
            if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }
    return true;
}

bool check(){
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0)){
                flag = false;
                break;
            }
    return flag;
}

二分图最大匹配

概念

交错路：一条路径，其中的边（点）的状态是交错的（非匹配边，匹配边，非匹配边，匹配边......）

增广路：以非匹配点为端点的路径，增广路的长度为奇数

性质

当二分图中不存在增广路时，此时的匹配为最大匹配

将增广路的边的状态翻转可以使匹配数 \(+1\)

匈牙利算法

每次寻找增广路

时间复杂度：\(O(nm)\)

\(code1\)

int n1,n2,m;
int h[4*N],e[4*M],ne[4*M],idx;
int match[N];
bool st[N];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool find(int x){
	for(int i=h[x];~i;i=ne[i]){
		int j=e[i];
        if(!st[j]){
			st[j]=true;
            if(match[j]==0||find(match[j])){
				match[j]=x;
                return true;
            }
        }
    }
    
    return false;
}

int main(){

    memset(h,-1,sizeof h);
    
    n1=read(),n2=read(),m=read();
    for(int i=1;i<=m;i++){
        int x,y;
        x=read();y=read();
        add(x,y+n1);
        add(y+n1,x);
    }

    int res=0;
    for(int i=1;i<=n1;i++){
        memset(st,false,sizeof st);
        if(find(i)) res++;
    }

    cout<<res;

    return 0;
}

\(code2\)

int n,m,e,u,v;
int ans=0,mp[maxn][maxn],match[maxn];
bool vis[maxn];

bool dfs(int u){
    for(int v=1;v<=m;v++){
        if(vis[v]==true||(!mp[u][v])) continue;
        vis[v]=true;
        if(match[v]==0||dfs(match[v])){
            match[v]=u;
            return true;
        }
    }
    return false; 
}

int main(){
    read(n),read(m),read(e);
    for(int i=1;i<=e;i++){
        read(u),read(v);
        mp[u][v]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) vis[j]=false;
        ans+=dfs(i);
    }
    cout<<ans<<endl;
    return 0;
}

*网络流可以跑到 \(O(\sqrt {n}m)\) ，但是有时候只能用匈牙利

例题

[CF1139E] Maximize Mex

CF1139E Maximize Mex

建图时分别将权值和集合建为两类点，题中的一个点即为图中的一条边

倒序处理所有操作，删边即变为加边，每次从上次答案处匹配

时间复杂度：\(O(n\times(权值+d))\)

霍尔定理

概念

完美匹配：当二分图的左右部点数量相同时才会谈完美匹配。完美匹配是所有点都是匹配点的一个匹配

定理：对于任何左（右）部点的子集 \(S\) ，与 \(S\) 相邻的右（左）部点的数量不小于 \(|S|\) ，满足该条件的二分图存在完美匹配

定理也可推广到左右部点点数不相同或是点的子集

例题

[CERC 2016] 二分毯 Bipartite Blanket

P3679 [CERC2016]二分毯 Bipartite Blanket

在左右部点分别找两个合法子集 \(S,T\) ，则 \(S \cup T\) 满足 \(V\) 被至少一个匹配 \(M\) 覆盖

若一个集合满足霍尔定理，那么它的子集也一定满足

因为将可行状态排过序，所以 \(\ge T-V\) 的部分即为后缀。二分或维护指针求出来边界的位置即可

例题

P4589 智力竞赛

P4589 [TJOI2018]智力竞赛

在一张 \(DAG\) 中找 \(n+1\) 条链进行覆盖（可相交），最大化没有被覆盖的点的权值

\(floyd\) 求传递闭包后跑二分图最大匹配，若不能覆盖就二分答案
P1129 矩阵游戏

P1129 [ZJOI2007] 矩阵游戏

将黑色格子所在的行和列连边，跑一遍最大匹配，若是完美匹配即可
P2825 游戏

P2825 [HEOI2016/TJOI2016]游戏

[LOJ 2057] 「TJOI / HEOI2016」游戏

把每行和每列中的合法非空子段抽象成一个点，对于每个可放炸弹的位置 \((i,j)\) ，从其所在的行内合法子段对应的节点想其所在的列内合法子段对应的节点连一条有向边

跑二分图匹配，最大匹配数即为答案
P3731 新型城市化

P3731 [HAOI2017]新型城市化

取补，补图是二分图

城市群即为补图中的独立集，最大城市群即为补图中最大独立集

定理：最大独立集= \(n-\) 最大匹配

给定一张二分图，要删一条边使得最大匹配 \(-1\) ，即求哪些边一定在最大匹配里

定理：若一条边一定在最大匹配中，则在最终的残量网络中，这条边一定满流，且这条边的两个顶点一定不在同一个强连通分量中 p

所以 \(Dinic+Tarjan\)

字符串

字符串哈希

P3370 【模板】字符串哈希

算法

把字符串转换为一个正整数来快速判断字符串是否相等

对于一个长度为 \(n\) 的字符串，其哈希值为 \(\sum_{i\ge 1}^{i\le n}s_i\times base^{n-i} \pmod P\) ，其中 \(base\) 和 \(P\) 是自选的

其中 \(base\) 称为底数，\(P\) 称为模数，都是自选的

感觉这么说比较抽象，其实就是设一个进制 \(x\) ，把这个串看成一个 \(x\) 进制数：

\(num=s_1\times x^0+s_2\times x^1+s_3\times x^2+...+s_n\times x^{n-1}\)

然后对一个比较大的质数取模

因此我们判断两个字符串的一个方法是直接判断哈希值是否相等（虽然有概率出错，解决方法见下文）

此外，我们也可快速算出字符串任意子串的哈希值。预处理出前缀哈希值，乘上 \(base\) 的若干次逆元即可

关于模数

模数一般用较大的质数，是为了减小冲突的概率

在实践中自然溢出(\(unsigned \ long \ long\))的冲突概率是最小的，毕竟这是一个 \(2^{64}\) 的模数

在 \(10^5\) 级别时可能会出现哈希冲突，可以用双模数

综上所述，最保险的哈希方法是自然溢出加上对大质数取模。

常用模数：1

这篇关于2021.07.16笔记-图论字符串1的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

2021.07.16笔记-图论 字符串1