蓝桥日记

2022-01-23

Word count: 6k | Reading time≈ 28 min

查漏补缺

补充：

1.若开超大数组爆栈 ,开全局
2.四位数的隐含条件？最小四位数不是 0000 而是 1000，回文数的话，是	1001
3.scanf有时候可以解决cin提交出现的TLE（比如要求在150ms内），大概可以提高个2~450ms，数据规模越大，提升越好
5.多组输入，参数初始化，要给放到循环中，好久不写忘了
6.RE错误，runtime error(运行时错误)就是程序运行到一半,程序就崩溃了。
7.while(cin>>n)多组输入 重复输入结果变了？Ⅰ.初始化没有做好，检查有没有需要初始化的Ⅱ.输入设计的不合理
8.递归：1、缩小规模 2、有结束条件
9.const 只是一个修饰符，不管怎么样 const int a;仍然是一个整型变量
10.位操作运算符，参与运算的量，按二进制位进行运算。包括位与(&)、位或(|)、位非(~)、位异或(^)左移(<<)、右移(>>)六种 。

数值处理

1.绝对值函数

1 2	abs() fabs()

头文件

1	#include<stdlib.h>

``判断单个字符是不是数：
1
2
3
4
5
char c ='5';
if(isdigit(c))
{
    cout<<"yes, is number"<<endl;
}

2.组合数公式

A _n^m = C_n^m × A_m^m 其中, A_m^m = m ! C_n^m =n!/( m! (n-m)! )

3.int 转 double

double res;

res = 6/8;
//结果 0
res = 1.0*6/8;
//有了1.0后，结果 0.75

4.memset()

int a[10];
int mp[100][100];

memset(a,0,sizeof(a));//0 、-1 、INF 才是有效的赋值   其它赋值结果不详
memset(mp,0,sizeof(mp));

头文件

1	#include<string.h>

5.取反函数 reverse()

reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数没有返回值

//the first condition
int a[10];
reverse(a,a+m);

//the second condition
string s;
reverse(s.begin(),s.end());

头文件

1	#include<algorithm>

6.排序函数 sort()

函数使用的排序方法是类似于快速排序的方法时间复杂度为n*log2(n)

//up sort （disabled）
int a[10]={9,6,3,8,5,2,7,4,1,0};  

sort(a,a+10);//a即地址，所以传入的是地址，原数组值改变

//drop sort
bool compare(int a,int b) 
	return a>b;

int a[10]={9,6,3,8,5,2,7,4,1,0};

sort(a,a+10,compare);//不需要对compare函数传参

头文件

1	#include<algorithm>

若给结构体排序出现失灵？

用于比较大小的变量肯定用错了

7. char[] 如何转 string ？如何用 printf 输出 string ？

char c[20];
string str = c;//直接初始化，完成转换

printf("%s\n",str.c_str());//c 输出 string
cout<<str<<endl; //c++ 输出 string

如果是单字符 char 转 string，上述如果照搬：【定义并立即初始化，初始化过程进行隐式类型转换】
1
2
char c ='a';
string str = c;//直接初始化，完成转换
编译报错。。。那该怎么做？

1）把定义和赋值分开，竟然是可行的。【定义未初始化，赋值过程进行隐式类型转换】

也就是说，string 初始化只能用字符串，想赋予一个字符。只能在初始化之外的操作（比如赋值）寻求可行性。当然这个问题2023-07-19才注意到，是因为平时习惯不初始化，只定义，另起一行赋值的习惯，所以一直以来初始化和赋值这两个概念我是模糊的，新习惯，新思路的养成确实会找补不少以前的问题。
1
2
3
char c = 'a';
string str ;
str = c;//跳过初始化直接赋值，完成转换
2）使用频率上和逻辑合理性上，我更推荐这个拼接。
1
2
3
char c = 'a';
string str ="";
str += c;
3）chatgpt 提供的一种，显式类型转换
1
2
3
 char c = 'a';
string str;
str = string(1, c);
补充一下初始化和赋值的概念

初始化：初始化是在创建变量时，为其赋予初始值。

赋值：赋值是将一个已经存在的变量重新赋予新的值。在赋值过程中，变量已经被声明和初始化

string str;不要以为这样就没有初始化了，int num;还记得不赋值直接用它是个随机值嘛，所以str是有默认值的，是个空串。

8.如何定义无穷大？

1	#define INF 0x3f3f3f3f

9.♥♥ 如何实现 string 单字符 s[i] 转字符串实现 string 查找函数的输入要求？（超高频，目前解决string函数输入最简单的方法）

1 2	string temp = str.substr(i,1);// s[i] ,'x' was transformed to "x" str.find(temp);

10.如何字符串char[] 转 int？

atoi()函数&头文件

全称： ascii to integer

1	#include<cstdlib>

1	int res = atoi(x);//x 为char[]类型，必须是字符数组

反之,也有itoa()；

1
2
3

int x;
char content[10];
itoa(x,content,10);//10指的是十进制，2~36进制均可

如果是单字符 char a 或者 string s[i]这又该怎么办？

//method 1
char a;
int res =a-'0';

//method 2
int res = s[i]-'0';

11.如何string 转 int？

//手写版
int stoi(string s)
{
    int res =0;
    for(int i=0; i<s.size(); i++)
    {
        res =res*10+ s[i]-'0';
    }
    return res;
}
//c11下支持stoi
#include<cstring>
int res = stoi(str);

12.如何 int 转 string ？

//目前只会一个笨方法
string itos(int x)
{
    string s="";
    if(x == 0)s = "0"+s;//x=0 进不了下面的循环
    while(x)
    {
        if(x%10 == 0)s = "0"+s;
        else if(x%10 == 1)s = "1"+s;
        else if(x%10 == 2)s = "2"+s;
        else if(x%10 == 3)s = "3"+s;
        else if(x%10 == 4)s = "4"+s;
        else if(x%10 == 5)s = "5"+s;
        else if(x%10 == 6)s = "6"+s;
        else if(x%10 == 7)s = "7"+s;
        else if(x%10 == 8)s = "8"+s;
        else if(x%10 == 9)s = "9"+s;

        x/=10;
    }
    return s;
}

输入输出问题

如何输出制表符？

1	printf("\t");

万能头文件

在c++下编译，如果突然忘了头文件可以用

1	#include<bits/stdc++.h>

C++下读取整行

1 2	string s; getline(cin,s);

其它输入

#include<cstdio>
#include<cstring>

cin>>x;
getchar();//吃掉回车，cin不吃回车，getline会吃，但我们不让他吃掉cin后面的那个回车
getline(cin,str);
getline(cin,str2);//getline会吃掉回车，所以getline之间不需要单独设置getchar()了

如何输出%？

1	//%% 转义后输出%

C/C++ 库文件替换

//c
#include<stdio.h>
#include<string.h>
//c++
#include<cstdio>
#include<cstring>
using namespace std;

Python 如何实现多组输入？

while  True:
    try:
       #...
    except:
        break

printf 填充

1 2	printf("%02d",h); //占两位，用0填充

STL容器

1.总结

	STL	特点
栈	stack	逆序输出括号匹配表达式求值
队列	queue	配合BFS扩展状态，哈夫曼树权重
动态数组	vector	存结果的数组，二维`mp[10]`，模拟图的邻接表（二维数组超存时）贼好用
散列表	map	键值对映射，查找效率高，做树种类统计贼好用，统计字串频率
优先队列	priority_queue	基于大顶堆 ,处理输入序列中最大，最小值
集合	set
字符串	string	做查找分割贼好用 string str; “01 qwe” int pos = str.find(“ “); str = str.substr(first_position,pos-first_position); “01”
	pair	适合作为存储一对值的结构体

2.pair

pair是将2个数据组合成一组数据，pair的实现是一个结构体

当一个函数需要返回2个数据的时候，可以选择pair

在创建pair对象时，必须提供两个类型名，两个对应的类型名的类型不必相同

1
2
3

pair<int,int> p;
cin>>p.first>>p.second;
cout<<p.first<<" "<<p.second<<endl;

3.散列表 map

基于红黑树，map就是将key和value放在一起来保存

头文件&定义

1 2	#include<map> map<string,int>mp;

insert

1	mp[key]=value;

output or statistics

1 2	mp[key]=value; mp[key]=value++;

circulate 循环

//for
for(map<string,int>::iterator it = mp.begin();it != mp.end();it ++){
    cout<<it->first<it->second;
    //取出的是pair类型，
    //key    it->first
    //value  it->second
}

判断是否为空键？

1 2	//if_key_exist 1:yes 0:no mp.count(key);

删除键key？

1	mp.erase(key);

查找键key？

map<string,int>::iterator it;
it = mp.find(s);
if(it==mp.end()){
    cout<<"xxx is not found"<<endl;
}

mp.clear();	清空所有键值对
mp.empty();	如果map为空，返回true，否则返回false

如何 map 迭代获取 string 所有子串？

模板如下，不太理解

#include<map>
for(int i=0;i<str.size();i++){
    for(int j=0;j<i;j++){
        string key = str.substr(j,i-j);
        map[key]++;
    }
}
//所有字串个数=n（n+1）/2 +1（空串）   ，如果考虑去重，如 “uuu”则再-2   “uuuu”则再-3

4.栈 stack

头文件&定义

1 2	#include<stack> stack<int> s;

出入栈、栈顶元素

//入栈
s.push();
//出栈
s.pop();
//返回栈顶元素
s.top();

容量&空栈判断

1 2	s.size(); s.empty();

提示

while()
{
    stack<int> s;
    //这样每次循环自动重新初始化，适合多组输入清空栈
}

5.队列 queue

头文件&定义

1 2	#include<queue> queue<int>q;

出入队列&取头尾元素

//
q.push();
q.pop();
//
q.front();
q.back();

容量&空队列判断

1 2	q.size(); q.empty();

如何利用 queue 完成树的层序遍历？

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef struct node BT;
struct node
{
    char data;
    BT*l,*r;
};

int p;
string s;
BT* create_bt_by_pre()
{
    BT* root;
    ++p;
    if(s[p]==',')root=NULL;
    else
    {
        root =new  BT;
        root->data = s[p];
        root->l=create_bt_by_pre();
        root->r=create_bt_by_pre();

    }
    return root;

}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        p=-1;
        cin>>s;
        BT* root = create_bt_by_pre();

        // level_traversal
        if(root)//root ==NULL 时不能进队列，有一个，nuLL的队列不是空队列，下面会执行null->l?
        {
            queue<BT*>q;
            q.push(root);
            while(!q.empty())
            {
                if(q.front()->l)q.push(q.front()->l);
                if(q.front()->r)q.push(q.front()->r);
                cout<<q.front()->data;
                q.pop();
            }
        }
        cout<<endl;

    }

}

自己实现的 queue 排序（以后用优先队列）

#include<iostream>
#include<string.h>
#include<queue>
#include<stdio.h>
#include<algorithm>
using namespace std;

struct node
{

};
int main()
{
    char s[300];
    while(~scanf("%s",s))
    {
        int len = strlen(s);
        int len_asc = len*8;

        int t[300];
        queue <int>q;
        memset(t,0,sizeof(t));
        int sum =0;
        for(int i =0; i<len; i++)
        {
            if(t[(int)s[i]] == 0)sum++;
            t[(int)s[i]]++;
        }


        len=sum;//有效长度
        int len_huf =0;
        //queue 分配一个排序数组t[]
        while(len!=1)
        {
            sort(t,t+300);
            for(int i=300-len; i<300; i++)
            {
                q.push(t[i]);
            }
            int f1=q.front();
            q.pop();
            int f2=q.front();
            q.pop();
            q.push(f1+f2);
            len_huf+=f1+f2;
            len--;
            int j=300-len;
            while(!q.empty())
            {
                t[j++]=q.front();
                q.pop();
            }

        }

        printf("%d %d %.1lf\n",len_asc,len_huf,1.0*len_asc/len_huf);

    }
}

如何用 queue 计算哈夫曼树叶子编码长度？

即，叶节点权重*高度，等价于求所有节点（除根节点）编码权重之和

//queue排序      以后用优先队列就好了
 queue <int>q;
 int t[300];
//queue 分配一个排序数组t[]
        while(len!=1)
        {
            //排序t[]
            sort(t,t+300);
            //进q
            for(int i=300-len; i<300; i++)
            {
                q.push(t[i]);
            }
            int f1=q.front();
            q.pop();
            int f2=q.front();
            q.pop();
            q.push(f1+f2);
            len_huf+=f1+f2;
            len--;
            //定义t[]起始j,准备出q
            int j=300-len;
            //进t[]
            while(!q.empty())
            {
                t[j++]=q.front();
                q.pop();
            }

        }

6.优先队列 priority_queue

queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的

头文件&定义

1 2	#include<queue> priority_queue<int>pq;

出入优先队列&访问队头元素

//
pq.push();
pq.pop();
//
pq.top();

优先队列容量&空优先队列判断

1 2	pq.size(); pq.empty();

如何用优先队列小顶堆，计算哈夫曼树的合并代价？

1	priority_queue<int,vector<int>,greater<int> >q;

7.字符串 string

仔细观察不难发现，下面讲到的方法中的字符无论是不是单个字符全都是双引号括起来的，单引号报错我记得是const char 错误，遇到了就是引号出问题了。

按下标查找

string s="abcda";
//
s.find('a');                     //first position output:0
s.rfind('a');                    //last position output:4

如果找不到返回什么？

1	string st1("babbabab");

1
2
3

cout << (st1.find('c', 0) == -1) << endl;//1 string:npos
cout << (st1.find('c', 0) == 4294967295) << endl;//1   两句均输出1，原因是计算机中-1和4294967295都表示为32个1（二进制）
cout << st1.find('a', 100) << endl;//4294967295   当查找的起始位置超出字符串长度时，按查找失败处理，返回npos

替换

1	s.replace(0,1,"11") //下标0开始，连续占用1个位置替换：11bcda

比较

1 2	string s2="abcda"; s.compare(s2) // s>s2返回值为1 =:0 <:-1

stirng 字典序比较【ASCII序】，其中，非空串>空串

截取一段(重要)

1 2	string s="abcdef"; str = s.substr(0,3) //0开始，截取3字节 abc

插入删除

1 2	s.insert(3,"asd") //插入到第三个位置 s.erase(0,2) //0开始，删除2字节 ,删除超过存在字节数，不要紧，结果就是空

删除字符串全部空格的一般思路？

一个是找，再一个是删

//delete all x from s
string x = " ";
while(s.find(x) != -1)
{
    p = s.find(x);
	s.erase(p,x_size);
}

8.可变数组 vector

头文件&定义

1 2	#include<vector> vector <int>arr;//一维可变数组，存遍历结果贼好用

输入

//input
v.push_back(1); //□   arr[0]
v.push_back(2);//□+□
v.push_back(3);//□+□+□

遍历

//condition 1  
//基于迭代器变量 vector<int>::iterator
for(vector<int>::iterator it =arr.begin();it!= arr.end();it++)
{
    cout<<*it<<endl;
}

//condition 2
for(int i=0;i<arr.size();i++)
{
    cout<<arr[i]<<endl;
}

vector 排序

1	sort(v.begin(),v.end());

如何删除最后一个元素？

作为结果数组，过程回溯用得上。

1	v.pop_back();

如何用 vector 模拟图的邻接表？

//平时用 vector<int>v; 足够了

//定义邻接表
vector<int>mp[50000];// 实际上是二维矩阵，模拟图的邻接表（二维数组超存时）贼好用
//存边（无向图为例）
int a,b;
cin>>a>>b;
mp[a].push_back(b);
mp[b].push_back(a);
//dfs遍历
void dfs(int v)
{
    vis[v]=1;
    for(int i=0;i<mp[v].size();i++)
    	if(vis[mp[v][i]] == 0)dfs(mp[v][i]);
}

多组输入时，如何清空 vector ？

1
2
3

while(){
    for(int i=1; i<=n; i++) mp[i].clear();
}

如何用 vector 实现无向图存储？

1
2
3

int a,b;
mp[a].push_back(b);
mp[b].push_back(a);

用 vector 实现无向图存储，遍历用时更短

//取值 比如a可到达的节点
for(int j=0;j<mp[a].size();j++)
{
    cout<<mp[a][j];
}

如何用 vector 实现二维数组存储？

/*
例如，存入
aaaaaaa
bbbb
ccccccccc
用 vector<int>temp 存 aaaaaaaa
再 array.push_back(temp)
依次按行存入整个二维矩阵
*/
vector<vector<int>>array;

for(int i=0;i<array.size();i++){
    for(int j=0;j<array[i].size();j++){
      //array[i][j]
    }
}

9.集合 set

set容器内默认有序，升序

作用	方法	说明
定义	set<type> s;	type 可以是任何基本类型或者容器
插入元素	s.insert(x)	将元素插入到集合中
删除元素	s.erase(x)	移除元素
查找元素	s.count(x)	判断集合中是否存在该元素
获取元素个数	s.size()	不会删除队尾元素
清空集合	s.clear()	删除集合中所有元素

头文件&定义

1 2	#include<set> set<int>s;

遍历

1
2
3

//by iterator迭代器
for(set<int>::iterator i=s.begin();i!=s.end();i++)//不总是 set<int> 这里的 int 是向 set<int>s 定义看齐
    cout<<*i<<endl; //注意指针运算符

复数比较

如何用结构体重载 <实现复数比较？

//比较复数a+bi 重载<
struct Complex
{
    int a;
    int b;
    bool operator< (Complex c) const{
        return a*a+b*b < c.a*c.a+c.b*c.b;//比较模大小
    }
    
};

链表问题

纠正一下下面的问题！返回值为指针没意义，改动的是地址

llist* ins(llist* head,int n)
{
   //...
    return head;

}


//等价 
void ins(llist* head,int n)
{
   //...

}

数组问题

纠正! 修改函数中的数组a，原数组也会变，数组作为函数参数，传递的是数组首地址，并不是复制一遍，属于值传递。

所以很多时候为了共享数组开全局的情况只要不是数组太大怕爆栈，都没必要开全局。

void f(int a[]);
{
    //...
}

int a[10];
f(a);

字符长度

//c
char ch[20];
int len =strlen(ch);
//c++
string str;
int len = str.length();

头文件

1 2	#include<string.h>//strlen #include<string>

BFS 模板

while(!q.empty())
   {
       int p = q.front();
       q.pop();

       for(int i=1; i<=n; i++)
       {
           if(!vis[i]&&ma[p][i])
           {
               //d[i]=d[p]+1;
               vis[i]=1;
               q.push(i);
           }
       }
   }

DFS模板

如何用 vector 存图优化 dfs，降低搜索时间？

//用vector 存边
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
//int mp[5000][5000]; too large
vector<int>mp[50000];
int vis[50000];
int n,m;

void dfs(int v)//优化后的dfs  按照以前写法o（n）2
{
    vis[v] =1;

    for(int i=0; i<(int)mp[v].size(); i++)
    {
        if(!vis[mp[v][i]])dfs(i);
    }



}

int main()
{

    int cir =0;
    while(~scanf("%d%d",&n,&m))
    {
        cir++;
        if( n==0&&m==0)break;
        //init
//        memset(mp,0,sizeof(mp));
        for(int i=1; i<=n; i++)
        {
//vector 清空  size置为0，空间大小还在
            mp[i].clear();
        }
        memset(vis,0,sizeof(vis));



        while(m--)
        {
            int a,b;
            cin>>a>>b;
//            mp[a][b]=mp[b][a]=1;
            mp[a].push_back(b);
            mp[b].push_back(a);
        }

        //the times of dfs //连通分量
        int co =0;
        for(int i=1; i<=n; i++)
        {
            if(!vis[i])
            {
                dfs(i);
                co++;
            }
        }

        printf("Case %d: %d\n",cir,co);
    }
}

vector 存图，如何取边？

//vector取值 
//拼出一个个之前输入的mp[i]  ,存的只是一个数字，试试mp[i][0]
	for (i)
		for (j)
            cout<<mp[i][j];

图算法总结

Prim:代码解决最小生成树/连通花费最低代价问题

Dijkstral:画图解决单源最短路/所有点距离某一点最短路径

floyd:O(n)3代码解决多元代价最短路问题

快速幂模板

更快速的计算幂运算

32 :2^5 乘 5次2 快速幂（101），乘两次时间上log（n）

//数字转二进制
f(int a,int b,int mod)
{
    while(b!=0)
    {
        //处理b%2
        
        b/=2;       
}



FastExponentiation(int a,int b,int mod)
{
    int ans =1;
    while(b!=0)
    {
        if(b%2==1)
        {
           ans*=a;
           ans%=mod;
        }
        b/=2;
        a*=a;
        a%=mod;
    }
    return ans;
}

如果数据是 long long ，那么有什么不同？

比如 a b 得是long long，那就意味着，a 在一开始要提前做一次取余， res=x1*x2 ;res%mod == (x1%mod)*(x2%mod) ,如果一开始不取余，就好像这个公式中的x1没有取余，就导致某些样例不通过。

循环问题

下面这种循环中执行break的三种情况？

int i; 
for(i=0;i<n;i++)...
{
    //...
}

1、没跑完，找到了 i<n

2、跑完了，找到了，计数变量 i = n-1

3、跑完了，没找到，i = n

for+break标识第一次匹配的位置

阶乘问题

要先了解阶乘计算数值骤增的特点，

若采用暴力计算，int 只能计算到 12！long long int 只能到20！

如何用组合数来优化阶乘计算，解决阶乘暴力计算过程值太大？

long long  C(int a,int b){
    long long res = 1;
    for(int i=a,j=1;j<=b;i--,j++){
        res =res * i / j;
    }
    return res;
}

大数加法模板

只用基本数据类型，十位数的运算就是到极限了，这时，想要进行大数运算，需要用大数加法

大数加法原理：小学列式法，一位一位的加，大于十就进位

#include<iostream>
#include<cstring>
#define MAXLEN 10000//规模  10000位数
using namespace std;
int main()
{
    string buffer;
    int a[10001],b[10001];//a、b为两个正整数
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    //逆序输入a
    cin>>buffer;
    for(int j=0, i=buffer.length()-1; i>=0; i--)
    {
        a[j++] = buffer[i]-'0';
    }
    //逆序输入b
    cin>>buffer;
    for(int j=0, i=buffer.length()-1; i>=0; i--)
    {
        b[j++] = buffer[i]-'0';
    }
    //计算
    for(int up=0, i=0; i<MAXLEN; i++)
    {
        int tmp  = a[i]+b[i] +up;
        a[i]=tmp%10;
        up = tmp/10;
    }
    //逆序输出逆序的a  逆逆得正序
    for(int i=MAXLEN; i>=0; i--)
    {
        if(a[i] !=0)
        {
            for(i=i; i>=0; i--)
            {
                cout<<a[i];
            }
        }
    }

}

如果使用了 string 容器，遇到两个数位数不齐，怎么办？

要么知道数据范围用char数组，要么把两个数中较小数高位补0 ，甚至最后两个数高位再一起补充一个前序0防止使用STL容器考虑不周造成的进位溢出。

上述操作在输出时（若结果非零）从第一个非零数开始输出即可避开这个前序0。

大数加法结果乱码原因？

往往是我（判断条件||赋值条件）搞混了字符‘0’ 和整数0。

结构体问题

结构体实例化

typedef struct node
{
	int data;
}Nickname;

int main()
{
    //实例化1
    struct node a;
    cout<<a.data<<endl;
    
    //实例化2
    Nickname b;   
    cout<<b.data<<endl;
}

并查集模板

用于判断连通图、求连通分量

1.初始化 Initial()

2.合并 Union(x,y) 路径压缩,合并顶点 x，y

3.查询 Find() 找爹

#include<iostream>
using namespace std;
int n,m;
int father[1010];
int height[1010];
void Initial(){
    for(int i=1;i<=n;i++){
        father[i]=i;//自己是自己的父亲
        height[i]=0;//高度为0
    }
}
int Find(int x){//找爹
    if(x !=father[x]){//找到根节点 才返回
        father[x] = Find(father[x]);
    }
    return father[x];
}
void Union(int x,int y){
    x =Find(x);
    y =Find(y);
    if(x!=y){
            if(height[x] < height[y]){ //矮子合并到高个子树上，整体高度不变
            father[x] =y;

        }else if(height[x]>height[y]){
            father[y]=x;
        }else {
            father[y] =x;
            height[x]++;
        }
    }
    return;
}
int main(){

    while(cin>>n>>m){
        if(n == m && n == 0)break;
        Initial();
        while(m--){
            int x,y;
                cin>>x>>y;
            Union(x,y);
            
        }
        int compenent =0;
        for(int i=1;i<=n;i++){
            if(Find(i) == i)compenent++;//连通分量个数，数数根节点
        }
        if(compenent == 1){
            cout<<"YES"<<endl;
        }else {
            cout<<"NO"<<endl;
        }
    }
}

树问题

如何判定是一颗树？

一个集合/一个连通分量

入度：根节点：0，其他节点：1

有可能会遇到编号不连续没有给出顶点从1开始编号观察样例有没有 2，3，4，5，6这样不是从1开始连续的，到时候遍历集合的时候跳过即可。

01背包问题

【动态规划】

有限制的选择问题

https://www.bilibili.com/video/BV1K4411X766?from=search&seid=11764982276319298611&spm_id_from=333.337.0.0

子序列和子串

定义：
所谓的子序列就是在原来序列中找出一部分组成的序列
举例：
12356710它的子序列有很多。比如：12,13 ,15,16,1356,137,…

子串定义：
子串指的是串中任意个连续的字符组成的子序列，称为该串的子串
举例：
假设字符串的长度为n，其非空子串的数目为n(n+1)/2个。

例如字符串“abc“的连续子串有 a,ab,abc,b,bc,c 最大连续子序列才是子串。

Donate

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.