沈阳微信网站,网站哪里备案,市场调研报告模板,wordpress菜单页面跳转1.图的存储 #xff08;1#xff09;.邻接矩阵 邻接矩阵可以借助stl中的vector,我们通过开一个二维矩阵,g[u]中存储的是u可以到达的点,定义如下
const int N 2e5 10;
vectorint g[N]
若是遇到带权图则定义如下
const int N 2e5 10;
vector pair int ,…1.图的存储 1.邻接矩阵 邻接矩阵可以借助stl中的vector,我们通过开一个二维矩阵,g[u]中存储的是u可以到达的点,定义如下
const int N 2e5 10;
vectorint 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
