5.8 训练周记

这两周主要学习了图论的基本存储方式，拓扑排序和并查集。但因时间原因还有一些不太清楚的地方。

目录

一.图的存储

二.拓扑排序

三.普通并查集 

---

一.图的存储

要对图进行 *** 作，我们首先得有张图。

目前学习的对图的存储方式：

1.邻接矩阵

2.邻接表

两种方式各有优劣。

总体上来看，邻接矩阵相对简单，对得到一条边的两个顶点，判断其为有无方向，然后两顶点按情况标记即可

      cin >> a >> b;
      if (gra[a][b] == 0) {
        gra[a][b] = 1;//有向边
      //gra[b][a] = 1;//无向边
      }

邻接矩阵虽然 *** 作简单，但是对空间有很大的浪费，所以稀疏图常采用邻接表存储

邻接表。抽象上来说，就是一个顶点数组，每个顶点对应着一串与其相连的顶点

。结构如下

由此我们可以轻易的遍历与一个顶点相连的所有子顶点（树形结构常用）

但是实现较为复杂，个人也是主要学习了另一种实现方式——vector

创建一个空二维vec，然后将每个子节点push进对应节点的vector中

cin >> a >> b;
gra[a].push_back(b);//改用邻接表存储
//gra[b].push_back(a_;//无向边

 这样的优点就是存储图时占用空间小，子节点访问方便，实现简单。

缺点是vector本身的特性导致节点数过多时效率较低。

  for (int x : gra[now])//访问子节点

二.拓扑排序

首先我们需要明确什么是拓扑排序，他是解决什么问题的

拓扑排序：

只有有向无环图(Directed Acyclic Graph，简称DAG )才有拓扑排序。
DAG必至少有一个入度为零的点和一个出度为零的点。

在拓扑排序中，对于任意一个有向边的起点和终点，在排序后起点总是在终点前。

从定义来看，有向边的起点总在终点前，有向边的起点不就是出度，终点不就是入度吗。所以我们可以从入度出发，每次pop出一个入度为0的顶点，然后将这个顶点链接的所有路线都删除，重复直到图的顶点被遍历完。如果仍然还存在顶点怎么办？说明这个图中存在环。所以拓扑排序常被用来判断图中有无成环。

还有，当 一件事情必须在另一件事情完成之后才能进行，因此，这种十分强调事件的先后顺序的问题也可以使用拓扑排序即可解决。

如：

 就是各个条件中存在联系，同时还强调先后顺序。所以我们可以将它转换为图论问题，用拓扑排序实现。思路为，每个顶点的入度即为被打败的次数。首先，第一名没有被打败过，入度为0，d出，并且剩下的所有被他打败的人的排名都提升了一位，再找出当前情况下的第二个“第一”重复此 *** 作

具体实现。

//#include
#include 
#include
#include
#include
#include
#include
#include
#include

同时，拓扑排序常被用于判断图里有无环

如：

题意简单概括就是判断一个图有没有环，只需要拓扑排序，然后记录拓扑的节点数，如果等于总节点数，也就是全部的节点都被pop了就没有环，反之则存在环

//#include
#include 
#include
#include
#include
#include
#include
#include
#include

三.普通并查集 

并查集是一种实现非常简单且用处广泛的数据结构。值得多磨一磨。就我目前学习的内容来看，并查集主要被用于判断联通，合并集合和计算联通块的个数，简单概括就是”并“和“查”

因为时间有限，带权并查集还没怎么学习，先搁一边了。先整理一下普通的并查集

常用的 *** 作为以下四步：

const int N = 1e4;
int pre[N];//每个下标节点的前驱节点
void init(int n) {//初始化
    for (int j = 0; j < n; j++) {
        pre[j] = j;
    }
}
int  find(int x) {//查找祖先
    if (pre[x] == x)return x;
    return pre[x] = find(pre[x]);
//return pre[x]==x?x:pre[x]=find(pre[x]);
}
 
void com(int a, int b) {//合并操作
    int t1=find(a),t2=find(b);
    if(t1==t1)
        return ;
    if(t1!=t1)//祖先不同，说明不是一个集合的，看情况进行合并
        pre[t1]=t2;
    
}
int is_sm(int x, int y) {//判断两顶点是否是一个集合的
    return find(x) == find(y);
}
 

虽然实现很简单，但是其中的find的优化思路很值得学习——如果两个子节点的祖先都为同一个节点。那么没必要每次查找的时候都沿路上的所有节点都访问一遍，直接将他们的父节点定义为祖先即可，也就是爸爸的爸爸就是我的爸爸。

这样find除了第一次使用的时候需要递归处理，其他时候都是O(1)的复杂度。

并查集的实现没什么好说的，接下来谈谈并查集的使用。

1.判断联通块

 这里先把修复顺序按时间排序，接下来就是常规的判断联通块 *** 作了。

其实很简单，一开始联通块为n个顶点，也就是各自都独立。每次查询到两个不同集合的顶点就将其合并，此时联通块个数减一。重复此 *** 作直到已有的关系都合并了，剩下的数量即为联通块的个数

（这题Python的输入好像爆时间了）

import copy
 
class node:
    x,y,t=0,0,0
    def __init__(self,x,y,t):
        self.x=x
        self.y=y
        self.t=t
pre=[]
def init(n):
    for i in range(n+1):
        pre.append(i)
def fnd(x):
    if pre[x]==x:
        return x
    else:
        pre[x]=fnd(pre[x])
        return pre[x]
def join(x,y):
    pre[fnd(y)]=fnd(x)
def judge(x,y):
    if fnd(x)==fnd(y):
        return True
    else:
        return False
 
n,m=map(int,input().split(' ',2))
 
l=[]
init(n)
for i in range(m):
    a,b,c=map(int,input().split())
    x=node(a,b,c)
    l.append(copy.deepcopy(x))
l=sorted(l,key=lambda x:x.t)
sum=0
ok=0
for i in range(m):
    t1=fnd(l[i].x)
    t2=fnd(l[i].y)
    if t1!=t2:
        sum=sum+1
        pre[t1]=t2
        if sum==n-1:
            print(l[i].t)
            ok=1
            break
if ok==0:
    print(-1)

接下来就是复杂一些的并查集 *** 作，删边

 思路：删边不可取，离线记录完所有删除的情况，用不会被处理的顶点建立初始的并查集。补顶点同时恢复边，记录连通块个数，但是因为是逆向处理，所以连通块增加时对应的答案应该是减少。

虽然思路出来了，但是debug还是花了好长时间....

#include 
#include
#include
#include
#include
#include
#include
#include

有些时候还要对合并 *** 作做一些处理，比如编号在前之类的

如zoj的一题

题意：给出n个顶点，每个顶点有对应的能量值，再给出m个顶点对表示初始图的联通情况。

最后给出Q个条件，query表示 查询某个顶点所在集合中能量最大的顶点编号（如果最大能量的顶点有相同则输出序号最小的）。destroy+顶点对表示删除该顶点之间的联通。

思路：

并查集做不到合并完然后删边，所以想到先得到查询数据然后根据删的边逆向并查集，每次删的边变为加上该边，就可以使用合并 *** 作了。既然是逆向离线处理，所以创建初始图的时候如果该边会被删除就不要加入初始图里。

最后是合并 *** 作，题目要求输出每个集合中能量最大的顶点，如果能量最大的有多个就输出编号小的，这个条件可以放到并查集合并 *** 作中处理——合并祖先顶点的时候优先把能量值大的顶点当作祖先顶点，小的那个合并进去。如果能量值相同则优先编号小的当作祖先。
重点看合并 *** 作，其他大同小异

int pw[N];
int pre[N];
struct node {
    int op, first, second;
}q[N];//记录选择，离线处理,e数组记录起始的图
paire[N];
int fnd(int k) {
    return pre[k] == k ? k : pre[k] = fnd(pre[k]);
}
void join(int a, int b) {//满足题目规则的合并
    int t1 = fnd(a), t2 = fnd(b);
    if (t1 != t2) {
        if(pw[t1]==pw[t2])//集合中最大能量根节点相同，选择序号最小的
            pre[max(t1, t2)] = min(t1, t2);//max并入min里
        else if (pw[t1] > pw[t2]) {
            pre[t2] = t1;//能量小的并入能力大的
        }
        else {
            pre[t1] = t2;
        }
    }
}