MST：最小生成树   Kruskal:借助并查集   定义边结构体，构造边   #include<iostream> #include<algorithm> #include<cmath> using namespace std; const int maxn=25; int father[maxn]; int height[maxn]; void Initial(int n){ for(int i=0;i<n;i++){ father[i]=i; height[i]=1; } } int Find(int x){ if(x!=father[x]){...

MST：最小生成树   Kruskal:借助并查集   定义边、点结构体，通过点，构造边   #include<iostream> #include<algorithm> #include<cmath> using namespace std; const int maxn=101; int father[maxn]; int height[maxn]; void Initial(int n){ for(int i=0;i<n;i++){ father[i]=i; height[i]=1; } } int Find(int x){ if(x!=fath...

MST：最小生成树   已修建视为成本为0   Kruskal:借助并查集   定义边结构体，升序，依次合并不在同一连通集里的点   #include<iostream> #include<algorithm> using namespace std; const int maxn=101; int father[maxn]; int height[maxn]; void Initial(int n){ for(int i=0;i<=n;i++){ father[i]=i; height[i]=1; } } int Find(int x){ if(x!=fathe...

MST：最小生成树   Kruskal:借助并查集   定义边结构体，升序，依次合并不在同一连通集里的点   #include<iostream> #include<algorithm> using namespace std; const int maxn=101; int father[maxn]; int height[maxn]; void Initial(int n){ for(int i=0;i<=n;i++){ father[i]=i; height[i]=1; } } int Find(int x){ if(x!=father[x]){ fathe...

MST：最小生成树 Kruskal:借助并查集   定义边结构体，升序，依次合并不在同一连通集里的点   最后遍历所有结点，检查是否全部连通   #include<iostream> #include<algorithm> using namespace std; const int maxn=101; int father[maxn]; int height[maxn]; void Initial(int n){ for(int i=0;i<=n;i++){ father[i]=i; height[i]=1; } } int Find(int x){ if(x!...

并查集解决团队划分问题（连通集） 总结：主要思路还是并查集，并查集的操作模板化，只用修改结构体即可 个人结点信息较多，故用结构体； 团伙由于包含人数、头目名字，且要按照字典序输出，故也用结构体  个人结点：名字、通话时长 团伙结点：人数、头目名字  map<string,int>Getindex： 名字→个人结点的下标，且可以判断是否为第一次出现 输入： 新人员→生成新节点 获取输入的2个人的结点下标 更新通话时长，合并 遍历：根据顶级联系人划分团伙（为减少开销，设置访问标记） 判断团伙条件 输出: #include<iostream> #include<stri...

- 并查集 #include<iostream> using namespace std; const int maxn=1000000; int Father[maxn]; int height[maxn]; bool visit[maxn];//使用的结点 void Initial(){ for(int i=0;i<maxn;i++){ Father[i]=i; height[i]=1; visit[i]=false; } return ; } int Find(int x){//路径压缩查找 if(x!=Father[x]){ Father[x]=Find(Father...

树的判定条件  单连通 一个根节点（入度为0） 无环（入度均不大于1或度数之和=结点数-1）  #include<iostream> using namespace std; const int maxn=10010; int Father[maxn]; int height[maxn]; int indegree[maxn];//入度 bool visit[maxn];//使用的结点 void Initial(){ for(int i=0;i<maxn;i++){ Father[i]=i; height[i]=1; indegree[i]=0; visit[i]=false...

本题默认一个结点最多只有一个孩子 并查集：每个结点指向其孩子（不可压缩路径）  #include<iostream> #include<string> using namespace std; const int maxn=27; int son[maxn]; void Initial(){//初始化 for(int i=0;i<maxn;i++){ son[i]=i; } return ; } bool isson(int x,int y,string s){//y是否为x后代 bool flag=false; int h=1; while(son[x]!=x)...

#include<iostream> using namespace std; const int maxn=1010; int Father[maxn]; int height[maxn]; void Initial(int n){ for(int i=0;i<=n;i++){ Father[i]=i; height[i]=1; } return ; } int Find(int x){//路径压缩查找 if(x!=Father[x]){ Father[x]=Find(Father[x]); } return Father[x]; } void Union(int x,in...

求连通分量个数——并查集  #include<iostream> using namespace std; const int maxn=1010; int city[maxn]; int height[maxn]; void Initial(int n){ for(int i=1;i<=n;i++){ city[i]=i; height[i]=1; } return ; } int Find(int x){//路径压缩查找 if(x!=city[x]){ city[x]=Find(city[x]); } return city[x]; } void Union(int x,...

map映射：书号→人数  #include<iostream> #include<map> using namespace std; int main(){ int n,m; int s[201];//输入数组 while(scanf("%d",&n)!=EOF){ scanf("%d",&m); map<int,int>reader;//书号→喜欢人数 for(int i=0;i<n;i++){ scanf("%d",&s[i]); reader[s[i]]++; } for(int i=0;i<n;i++){ if(r...

map以红黑树实现：字典序 迭代器可以++、--，但不支持+1  #include<iostream> #include<string> #include<map> using namespace std; int main(){ int n; string number,timein,timeout;//证件号、进入时间，退出时间 while(scanf("%d",&n)!=EOF){ map<string,string>First; map<string,string>Last; while(n--){ cin>&g...

计数排序或者映射均可  #include<iostream> #include<map> using namespace std; int main(){ int n; while(scanf("%d",&n)!=EOF){ if(n==0)break; map<int,int>mymap; while(n--){ int score; scanf("%d",&score); mymap[score]++; } int x; scanf("%d",&x); printf("%d\n",mymap[x]); } return 0; }