新生讲课——图和并查集

1.图的存储

        （1）.邻接矩阵

           邻接矩阵可以借助stl中的vector,我们通过开一个二维矩阵,g[u]中存储的是u可以到达的点,定义如下

const int N = 2e5 + 10;
vector<int> g[N]

若是遇到带权图则定义如下

const int N = 2e5 + 10;
vector <pair <int , int> > g[N];

其中g[u][i].first表示u可以到达的点v,g[u][i].second表示u到达v的这条边的权值

邻接矩阵的遍历方法如下

int n;
vector <int> g[N];void dfs(int u)
{vis[u] = 1;for(int i = 0 ; i < g[u].size() ; i++){int j = g[u][i];if(vis[j]){continue;}dfs(j);}    
}

        (2).链式前向星

        其实就是以链表的形式存储图,实现如下

int h[N],e[N],w[N],ne[N],idx;
void add(int a,int b,int c)
{e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx++;
}int main()
{memset(h , -1 , sizeof h)
}

其中e[idx]表示idx这个位置存储的点u,ne[idx]存储u指向的点的下标,也就是e[ne[idx]]表示的就是v并且u指向v,w[idx]表示的是u到v点的边权,h[u]表示的是以u为起点的最后一条边遍历的时候帮助我们开始遍历以u为起点的路径,遍历方法如下

int h[N],e[N],w[N],ne[N],idx;
bool vis[N];void add(int a,int b,int c)
{e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx++;
}void dfs(int u)
{vis[u] = 1;for(int i = h[u] ; i != -1 ; i = ne[i]){int j = e[i];if(vis[j]){continue;}dfs(j);}
}

例题1

P3916 图的遍历 - 洛谷 | 计算机科学教育新生态

2.并查集

并查集是一种基础数据结构,通常帮助我们解决元素之间的杂乱关系,通过并查集归纳之后,杂乱的元素会变成一个个团体,每一个团体都有一个祖宗,我们可以O(log(n))的复杂度查询到每个团的祖宗,而祖宗相同的两个元素说明它们在同一个团中,并查集的实现如下

int p[N];int find(int u)
{if(p[u] != u){p[u] = find(p[u]);}return p[u];
}

这里的p[i]表示的实际含义就是i现在所在团体的祖宗,这里的find函数则可以帮助我们找到u的祖宗

for(int i = 1 ; i <= n ; i++)
{p[i] = i;
}

接下来给出合并u和v的代码,即将u和v所在团体合并成一个团体

void merge(int u,int v)
{int pu = find(u),pv = find(v);if(pu != pv){p[pu] = pv;}
}

这里首先我们先找到u和v当前所在团体的祖宗,若u和v的祖宗不同说明u和v不在一个团体,否则说明两个点在一个团体则不需要再合并,若两点不在一个团体则我们让u的祖宗的祖宗变成v的祖宗,如此一来原来祖宗为pu的点祖宗都变为pv,实际的含义就是将u所在团体融入到了v所在团体。

现在再来说一下这里的find函数,根据刚才的merge函数可以发现我们每次合并只是将u团体的祖宗的祖宗进行了改变,而不是将u团体中每个元素都改变,也正因如此复杂度得到大幅度的优化,从O(n)降低到O(logh(n)),也正因如此我们之后如果要查询i点祖宗的时候我们不知道i所在团体的祖宗是否跟别的团体合并,因此我们要顺藤摸瓜的去找当前i点的祖宗,在一个团体中只有祖宗的p[i] == i,其余的点p[j]记录的都是自己之前的上级,因此我们要一点一点的往上爬,直到找到当前团体的祖宗,然后返回,而这里通过压缩路径的形式,我们将沿途的所有点的祖宗都进行了修改(此处可画图演示)

板子题

P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态

P1551 亲戚 - 洛谷 | 计算机科学教育新生态

宏观概念的团体

P1892 [BalticOI 2003] 团伙 - 洛谷 | 计算机科学教育新生态

正难则反

P1197 [JSOI2008] 星球大战 - 洛谷 | 计算机科学教育新生态

带边权并查集

P2024 [NOI2001] 食物链 - 洛谷 | 计算机科学教育新生态

P5092 [USACO04OPEN] Cube Stacking - 洛谷 | 计算机科学教育新生态

比赛中出现的并查集相关题型

C-猪猪养成计划1_牛客小白月赛109

D-隐匿社交网络_牛客周赛 Round 77