上午：

并查集网课（正月点灯笼）

下面是例题：

//并查集找环 /* 题解： 【1】用一个parent[]；产生联系 【2】将点与点合并时，分别找到两点的根节点合并 【3】如果两个点的根节点相同就说明，这里有一个环 （优化）【4】将根连在一起时可以加一个判断高度的， 将矮的加到高的上，这样最大的高度不会变 */ #include<stdio.h> //将数组全部赋值为； void initialise(int *parent,int *rank) {for(int i=0;i<6;i++){parent[i]=-1;rank[i]=0;} } int find_root(int num,int *parent) { // if(num_root==num) // return num; // else // { // return( parent[num]=find_root(parent[num]); // }int num_root=num;while(parent[num_root]!=-1){//将自己直接连接到父亲结点的num_root=parent[num_root];//}return num_root; }//合并x,y（当它俩根节点相同不用合并时返回0，否则返回1 int combine(int x,int y,int *parent,int *rank) {int x_root=find_root(x,parent);int y_root=find_root(y,parent);if(x_root==y_root){return 0;}else{//即，x比y高，将y_root连接到x_root上来if(rank[x_root]>rank[y_root])parent[y_root]=x_root;else if(rank[x_root]<rank[y_root])parent[x_root]=y_root;else{parent[x_root]=y_root;rank[y_root]++;}return 1;} } int main() {int parent[10000];int rank[10000];//树的高度//将parent数组全部赋值为-1（可用于判断是否为根节点）initialise(parent,rank);//这样写代表这两个之间被线所连接int line[6][2]={{0,1},{1,2},{1,3},{3,4},{2,4},{2,5}};for(int i=0;i<6;i++){int x=line[i][0];int y=line[i][1];int book=combine(x,y,parent,rank);if(book==0){printf("Find a cycle.\n");return 0;}}printf("Never find a cycle.\n");return 0; }

下午：

亲戚

这个题和上面那个一样

/* 思路： 【1】就是要将前一个和后一个联系起来 【2】即，将有亲戚关系的一群人建成一棵树（不一定为1棵），形成森林 【3】然后找他们的根节点，如果根节点相同就是一棵树上，有亲戚关系 注意： 是要将m2根节点变成m1根节点的父亲 数组大小要看题目的数据范围 先要将自己的父亲赋初值为自己本身，后面才能以此来判断 */ #include<stdio.h> int father[100000]; int findroot(int m1) {//当自己的父亲为自己时，自己就是根节点if(father[m1]==m1)return m1;elsereturn father[m1]=findroot(father[m1]); } int main() {int n,m,p;scanf("%d %d %d",&n,&m,&p);//先将每个人的父亲初始化为自己（方便找根节点）for(int i=1; i<=n; i++){father[i]=i;}for(int i=1; i<=m; i++){int m1,m2;scanf("%d %d",&m1,&m2);if(findroot(m1)!=findroot(m2))father[findroot(m1)]=findroot(m2);//将两点的根节点连起来//father[m1]=m2;}for(int i=1; i<=p; i++){int p1,p2;scanf("%d %d",&p1,&p2);//如果根节点是一样的，那么就在同一棵树上if(findroot(p1)==findroot(p2)){printf("Yes\n");}elseprintf("No\n");}return 0; }

P1035新二叉树

//别在洛谷用getchar()； //如果一个个输入字符就用cin>>,别用scanf搭配getchar() /* 思路： 【1】直接把树的结点联系起来了 【2】然后按前序遍历，输出 【3】这个题最重要的是要将那一行三个字符联系起来 （所以使用了一个结构体） */ #include<bits/stdc++.h> using namespace std; typedef struct node {char data;char left;char right; }Node; Node tree[30]; int n; void preorder(char root) {if(root=='*')return;for(int i=0;i<n;i++){if(root==tree[i].data){printf("%c",root);preorder(tree[i].left);preorder(tree[i].right);}} } int main() {scanf("%d",&n);char ch;for(int i=0;i<n;i++){//一定要注意字符输入//别用会错（已试毒） //getchar();//吸收回车符cin>>tree[i].data>>tree[i].left>>tree[i].right;}char root=tree[0].data;preorder(root);printf("\n");return 0; }

晚上：

P4913二叉树的深度

（应该是深搜）

这个题又和上面那个新二叉树（异曲同工）

#include<stdio.h> typedef struct node {int left;int right; }Node; int n; Node Tree[100000]; int max=0; //结点和高度 void findhigh(int dot,int high) {if(dot==0){if(high>max)max=high;return;}findhigh(Tree[dot].left,high+1);findhigh(Tree[dot].right,high+1); } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d %d",&Tree[i].left,&Tree[i].right);}findhigh(1,1);printf("%d",max-1);return 0; }

总结

以上是生活随笔为你收集整理的2021.1.20的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。