计算机机试-图 -并查集

机试常考1.dfs/bfs2.并查集3.单源最短路径 dijstrala算法并查集1.每个节点的初始化 定义一个初始化每个节点为他本身序号注意推荐初始化时对节点编号为 1--n这样编号 在并查集和图论中不易出错初始化、遍历、输入校验都围绕 1~n 展开形成闭环如果初始化为0-n,则题意是遍历1-n节点 那么 0节点单独成为一个连通图浪费了一个节点const int N 1000; int father[N];//定义father数组为其节点的父节点标记 int high[N];定义树的高度 void InitTree(int n){ for(int i 0;in;i){ high[i] 0;//初始其高度 father[i] i;//初始化为本身 在有些书中为 -1 }2.查找父节点 类似于用其父节点去找父节点int Find(u){ if(ufather[u]) return u; else{ father[u] Find(father[u]);//优化每次查找到的父节点直接标记为根节点使得树扁平 return father[u]; } }4.两个树的合并 改变其父节点的值即可void unionTree(int u,int v){ int uroot Find(u);//值为u的根节点为 int vroot Find(v);//值为v的根节点为 //改变v这颗树的节点//小树挂高树 if(uroot!vroot){ if(high[uroot]high[vroot]) father[vroot] uroot;//小树挂大树 else if(high[uroot]high[vroot]) father[uroot] vroot; else{ father[vroot] uroot;//随便挂一颗树 high[uroot];//高度 } } }题目1畅通工程_牛客题霸_牛客网 并查集的利用 每当两个通路合并之后 其道路数减一#includebits/stdc.h using namespace std; const int N 1010; int father[N]; int setcount;//道路的数量 void InitTree(int n){ for(int i 0;in;i){ father[i] i; } }//初始化 int FindTree(int u){ if(ufather[u]) return u; else{ father[u] FindTree(father[u]); return father[u]; }//找根节点 } void UnionTree(int u,int v){ int uroot FindTree(u);//合并 int vroot FindTree(v); if(uroot!vroot) setcount--;//合并之后道路的数量减1 father[vroot] uroot; } int main(){ int n,m; while(scanf(%d%d,n,m)!EOF){ if(n0) break; InitTree(n1);//初始化 1-n个 setcount n; for(int i 0;im;i){ int v,u;//输入道路 scanf(%d%d,v,u); UnionTree(u,v);//进行合并 } printf(%d\n,setcount-1); } return 0; }2.这是一颗树吗3409. 这是一棵树吗 - AcWing题库思路1.利用并查集的基本功能union进行合并树 2.为-1-1 则break 3.如果为0 0 则要么读完一组数据要么为空树 printf()之后 还需重置基本的数据结构 4. 如果是其他的 则变数,节点数组记录是否出现过如果节点数大于2则不是 如果其父节点一样则相乘了环ifFind(u) Find(v)或者edgeCount ! vertexCount 1 不是连通子图了#includebits/stdc.h using namespace std; const int N 10001; int father[N]; void InitTree(int n){ for(int i 0;in;i){ father[i] i; } } int FindTree(int u ){ if(ufather[u]) return u; else{ father[u] FindTree(father[u]); return father[u]; } } void UnionTree(int u,int v){ int uroot FindTree(u); int vroot FindTree(v); father[vroot] uroot; } //并查集的初始化找根节点合并 int main(){ int u,v; InitTree(10001); //先初始化 int edgeCount 0;//边数 int vertexCount 0;//节点数 vectorint inDegree(10001); //记录入度 vectorint vertex(10001); //记录是否出现过vector[i] bool isOk true;//判断是否为树 int caseindex 1; while(1){ scanf(%d%d,u,v); if(u-1v-1) break; else if(u 0 v0){//此时完成一次数据输入 //一个图的边记录完成 //检查是否为一颗树 if(vertexCount!edgeCount1)//没有构成连通子图 isOk false; if(vertexCount 0 edgeCount 0)//特例 isOk true;//空树的情况 if(isOk true) printf(Case %d is a tree.\n,caseindex); else printf(Case %d is not a tree.\n,caseindex); //当v和u为00时候重置输入另外一组数据 //重置 InitTree(10001); //一组数据的初始化 edgeCount 0; vertexCount 0; for(int i 0;i10001;i){ vertex[i] 0; inDegree[i] 0; } isOk true; caseindex; } else{ //往当前的图加入新边 edgeCount; if(vertex[u]0){ vertex[u] 1; vertexCount; //变树增加 u节点 } if(vertex[v]0){ vertex[v] 1; vertexCount;//v节点 } //判断u和v是否之间有连同 if(FindTree(u)FindTree(v)) //出现了环 isOk false; else UnionTree(u,v);//连接在一起 inDegree[v];//自增 if(inDegree[v]2) isOk false; //不能退出要把全部的边全读完之后退出 } } return 0; }.4连通图_牛客题霸_牛客网找联通图如果并查集合并之后联通则其根节点为1如果存在两个联通的根节点为本身 则存在多个联通分量在构建并查集的初始化时 节点编号从1-n开始这样不易出错遍历时也不易全联通 说明每一个节点的根节点都一样非联通 说明 有节点的根节点不一样#includebits/stdc.h using namespace std; const int N 1010; int father[N]; int high[N];//树的高度 void InitTree(int n){ for(int i 1;in;i){//初始化遍历从1-n这样编号 father[i] i; high[i] 0; //初始化高度 }//从1-n进行初始化节点编号 } int FindTree(int u){ if(u father[u]) return u; else{ father[u] FindTree(father[u]); return father[u]; } } //查根节点 void UnionTree(int u,int v){ int uroot FindTree(u); int vroot FindTree(v);//找各自的根 if(uroot ! vroot){ if(high[uroot]high[vroot])//小树挂大树 father[vroot] uroot; else if(high[uroot]high[vroot]) father[uroot] vroot; else{ father[uroot] vroot;//相同则任意但高度增加 high[vroot]; } } return ; }//合并 int main(){ int n,m; while(cinnm){ if(n0m0) break; InitTree(n); while(m--){ int a,b; cinab; UnionTree(a,b);//合并 } int answer 0; for(int i 1;in;i){//判断是否连通图的思维逻辑 if(FindTree(i) i)// 如果存在节点的根节点为其本身则为一个分量 answer; //全部联通则其父节点都为1 }//节点编号从1-n编号 if(answer!1) coutNO\n; else coutYES\n; } return 0; }5.利用并查集 来判断其连通分支数1如果find(i) i为本身 并且以前访问过visit[i] true 则联通数加12. 利用一个visit[]数组进行定义是否被访问过#includebits/stdc.h using namespace std; const int N 1000001; int father[N]; int high[N]; int visit[N];//判断是否访问过 void InitTree(){ for(int i 1;iN;i){ father[i] i; high[i] 0; visit[i] false;//初始化为未访问 } } int FindTree(int u){ if(ufather[u]) return u; else{ father[u] FindTree(father[u]); return father[u]; } } void UnionTree(int u,int v){ int uroot FindTree(u); int vroot FindTree(v); if(uroot!vroot){ if(high[uroot]high[vroot]) father[vroot] uroot; else if(high[uroot]high[vroot]) father[uroot] vroot; else{ father[vroot] uroot;//注意这点原始高度加1 high[uroot];//高度加1 } } return; } int main(){ int n,m; int answer 0; InitTree(); while(cinnm){ UnionTree(n,m); visit[n] true;//标记为访问 visit[m] true; } for(int i 1;iN;i){ if(FindTree(i)ivisit[i])//判断条件 answer; } coutanswer; return 0; }