数据结构算法整理

直接插入排序

稳定的排序算法
题目：用插入排序对一组数据排序。
问题描述：
输入一个长度为n(3<n<100)的整数数组，实现用插入排序对数组中的元素排序，并输出前三趟排序后的数据。
输入格式:
首先输入串的长度n，然后输入整数数组n.
输出格式:
在三行上输出前三趟插入排序后的数组。
样例输入:
8
17 46 32 87 58 9 50 38
样例输出:
17 46 32 87 58 9 50 38
17 32 46 87 58 9 50 38
17 32 46 87 58 9 50 38

#include<iostream>
using namespace std;
int main()
{
 int number_size;
 int data[105];
 cin >> number_size;
 for (int i = 1; i <= number_size; i++)
 {
  cin >> data[i];
 }
 int temp = 0;
 for (int i = 2; i <= 4; i++)//如果要完整排完只需要将i的出循环条件设置为i<=number_size即可
 {
  for (int j = 1; j < i; j++)
  {
   if (data[j] > data[i])
   {
    temp = data[j];
    data[j] = data[i];
    for (int x = i; x > j+1; x--)
    {
     data[x] = data[x - 1];
    }
    data[j + 1] = temp;
   }
  }
  for (int i = 1; i <= number_size; i++)
  {
   cout << data[i] << " ";
  }
  cout << endl;
 }
 return 0;
}

希尔排序

不稳定的排序方法
题目：用希尔排序对一组数据排序。
问题描述：
输入一个长度为n（n<100）的整数数组，并实现用希尔排序对数组中的元素排序，输出第一趟排序后的数据。(希尔排序中的增量设置为increment=n/2向下取整，increment=increment/2向下取整，直到increment=1)
输入格式:
首先输入串的长度n，然后输入整数数组.
输出格式:
输出第一趟希尔排序后的数组。
样例输入:
8
48 26 66 57 32 85 55 19
样例输出:
32 26 55 19 48 85 66 57
将每个分组的元素都记录在vector中,然后用sort排完序之后又放回到原数组中,注意每排一次都要清空vector.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int input[105];
int number_size;
vector<int>vec;
int main()
{
 cin >> number_size;
 for (int i = 1; i <= number_size; i++)
 {
  cin >> input[i];
 }
 int gap = number_size / 2;//如果要完整排完只需要再加一个循环使得gap减到1就可以了
 for (int i = 1; i <= gap; i++)
 {
  for (int j = 0; j < number_size / gap; j++)//注意这里j的出循环条件
  {
   vec.push_back(input[i + j * gap]);
  }
  sort(vec.begin(), vec.end());
  int cnt = 0;
  for (int j = 0; j < number_size / gap; j++)
  {
   input[i + j * gap] = vec[cnt++];
  }
  vec.clear();
 }
 for (int i = 1; i <= number_size; i++)
 {
  cout << input[i] << " ";
 }
 cout << endl;
 return 0;
}

快速排序

不稳定的排序方法
题目：快速排序
问题描述
采用快速排序算法，排序输入的n个整数，prvotkey（枢轴）每次选取数组第一个数。
输出快速排序第一趟排序的结果。
输入格式
输入的第一行包括一个整数n(1<=n<=100)。
接下来的一行包括n个整数，空格隔开。
输出格式
按照要求排序后输出，由空格分隔。
样例输入
9
50 10 90 30 70 40 80 60 20
样例输出
20 10 40 30 50 70 80 60 90

算法简述：首先任意选取一个记录（通常可选第一个记录）作为枢轴（pivot），然后按下述原则重新排列其余记录：
附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指的位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录相互交换，重复这两步直到low == high为止。
其实就是从high所指的位置起向前搜索找到第一个关键字小于pivotkey的记录，直接放到原来pivotkey元素所在的数组位置，等到一趟排序结束后，再把pivotkey元素填入到空缺的位置上。

#include<iostream>
using namespace std;
int number_size;
int input[105];
int main()
{
 cin >> number_size;
 for (int i = 1; i <= number_size; i++)
 {
  cin >> input[i];
 }
 int pivot = input[1];
 int low = 1;
 int high = number_size;
 while (low < high)
 {
  while (low<high && input[high]>=pivot)//一定是>=而不是＞，书上快排算法就是这样实现的
   high--;
  input[low] = input[high];
  while (low < high && input[low] <= pivot)
   low++;
  input[high] = input[low];
 }
 input[low] = pivot;//此时low == high;
 //QSort(1,low-1);
 //QSort(low+1,number_size);
 for (int i = 1; i <= number_size; i++)
 {
  cout << input[i] << " ";
 }
 cout << endl;
 return 0;
 //如果要完整排完则要将while循环放在QSort函数中，然后枢轴左右递归调用，见while下的注释。
}

堆排序

不稳定的排序方法
堆排序
题目描述：编写堆排序算法，建立小顶堆，测试数据为整数。

输入：
第一行是待排序数据元素的个数（小于100）； 第二行是待排序的数据元素。

输出：
建立小顶堆的结果。

样例输入：
10
50 36 41 19 23 4 20 18 12 22

样例输出：
4 12 20 18 22 41 50 36 19 23

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
vector<int>vec;
int number_size;
int main()
{
 int value;
 cin >> number_size;
 for (int i = 1; i <= number_size; i++)
 {
  cin >> value;
  vec.push_back(value);
 }
 make_heap(vec.begin(), vec.end(), greater<int>());//小顶堆，默认是大顶堆，别忘记functional头文件
 for (int i = 0; i < number_size; i++)
 {
  cout << vec[i] << " ";
 }
 cout << endl;
 return 0;
}

归并排序

稳定的排序方法
题目：归并排序
问题描述
采用归并排序的方式，将两个已排序的数组，合并为一个数组并输出。
输入格式
输入第一行包含M N两个数，分别是第一和第二两个数组长度，空格分隔。M<100,N<100。
第二行为第一个已排序的数组，空格分隔
第三行为第二个已排序的数组，空格分隔
输出格式
输出排序好的从小到大数组，空格分隔
样例输入
4 4
1 2 3 4
2 3 4 5
样例输出
1 2 2 3 3 4 4 5

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>vec;
int input1[105];
int input2[105];
int number_size1, number_size2;
int main()
{
 cin >> number_size1>>number_size2;
 for (int i = 1; i <= number_size1; i++)
 {
  cin >> input1[i];
 }
 for (int i = 1; i <= number_size2; i++)
 {
  cin >> input2[i];
 }
 vec.resize(number_size1 + number_size2);//一定要给vec分配内存，否则会报错。
 merge(&input1[1], &input1[number_size1+1], &input2[1], &input2[number_size2+1], vec.begin());//第二个参数和第四个参数一定是最后一个元素的后一个位置
 for (int i = 0; i < number_size1+number_size2; i++)
 {
  cout << vec[i] << " ";
 }
 cout << endl;
 return 0;
}

二分查找

题目描述
DL 算缘分算得很烦闷，所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了，所以技术上不成问题，于是他就想玩点新花招。

DL 的视力真的很不错，竟然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己好视力的借口——他看清远方瓶子的个数后从某个位置发球，这样就能打倒一定数量的瓶子。

1 OOO

2 OOOO

3 O

4 OO

如上图，每个“O”代表一个瓶子。如果 DL 想要打倒 3 个瓶子就在 1 位置发球，想要打倒 4 个瓶子就在 2 位置发球。

现在他想要打倒 m 个瓶子。他告诉你每个位置的瓶子数，请你给他一个发球位置。

输入格式
输入文件名为 bowling.in。

第一行包含一个正整数 n，表示位置数。

第二行包含 n 个正整数，第 i 个数。表示第 i 个位置的瓶子数，保证各个位置的瓶子数不同。

第三行包含一个正整数 Q，表示 DL 发球的次数。

第四行至文件末尾，每行包含一个正整数 m，表示 DL 需要打倒 m 个瓶子。

输出格式
输出文件名为 bowling.out。

共 Q 行。每行包含一个整数，第 i 行的整数表示 DL 第 i 次的发球位置。若无解，则输出 0。

输入输出样例
输入 #1复制
5
1 2 4 3 5
2
4
7
输出 #1复制
3
0
说明/提示
【数据范围】

对于 50%的数据，1 ≤ n,Q ≤ 1000，1 ≤ai,M ≤ 10^5

对于 100%的数据，1 ≤ n,Q ≤ 100000，1 ≤ai,M ≤ 10^9

题目来自洛谷原题

#include<iostream>
#include<algorithm>
using namespace std;
struct Elem
{
 int position;
 int ball_number;
};
Elem elem[100005];
int position, aim, times;
bool cmp(Elem& a, Elem& b)
{
 return a.ball_number < b.ball_number;
}
int main()
{
 cin >> position;
 for (int i = 1; i <= position; i++)
 {
  elem[i].position = i;
  cin >> elem[i].ball_number;
 }
 sort(&elem[1], &elem[position+1], cmp);
 /*for (int i = 1; i <= position; i++)
 {
  cout << elem[i].position << " " << elem[i].ball_number << endl;
 }*/
 cin >> times;
 for (int i = 1; i <= times; i++)
 {
  cin >> aim;
  int left = 1;
  int right = position;
  int position_number = 0;
  while (left <= right)//注意这个循环条件不能没有等号
  {
   int mid = (left + right)/ 2;
   if (aim == elem[mid].ball_number)
   {
    position_number = mid;
    break;
   }
   else if (aim > elem[mid].ball_number)
   {
    left = mid + 1;
   }
   else if (aim < elem[mid].ball_number)
   {
    right = mid - 1;
   }
  }
  if (position_number == 0)
  {
   cout << 0 << endl;
   continue;
  }
  cout << elem[position_number].position << endl;
 }
 return 0;
}

二分的左闭右开写法，首次接触左闭右开神教，和STL函数统一起来。

#include<iostream>
#include<algorithm>
using namespace std;
struct Elem
{
 int position;
 int ball_number;
};
Elem elem[100005];
int position, aim, times, position_number;
bool cmp(Elem& a, Elem& b)
{
 return a.ball_number < b.ball_number;
}
bool binary_search(int l, int r,int aim)
{
 while (r - 1 >= l)//这里一定要有等号，否则退出循环的时候该区间内是两个元素
 {
  int mid = l + (r - l) / 2;
  if (aim == elem[mid].ball_number)
  {
   position_number = mid;
   return true;
  }
  else if (aim > elem[mid].ball_number)
  {
   l = mid + 1;
  }
  else if (aim < elem[mid].ball_number)
  {
   r = mid;
  }
 }
 return false;
}
int main()
{
 cin >> position;
 for (int i = 1; i <= position; i++)
 {
  elem[i].position = i;
  cin >> elem[i].ball_number;
 }
 sort(&elem[1], &elem[position+1], cmp);
 cin >> times;
 for (int i = 1; i <= times; i++)
 {
  cin >> aim;
  int left = 1;
  int right = position + 1;//一定要注意是左开右闭模式，最开始的right值也应该在原基础上加一
  if (binary_search(left,right,aim))
  {
   cout << elem[position_number].position << endl;
   continue;
  }
  else
  {
   cout << 0 << endl;
  }
 }
 return 0;
}

第一种写法显然是左闭右闭的模式，标志是left和right都能取到，所以在调整right是和left相对应，为mid-1；第二种写法是左闭右开的模式，标志是只有left点能取到，而right点只能取到它的前一个。所以在调整right时和left不相同，为mid,因为mid这一点取不到，所以实际上还是取到mid-1。
两种写法的right有所不同，循环的条件也对应不同。统一来讲就是都是保证left和right区间内只有一个元素，所以左闭右闭的写法中需要left == right，而左闭右开的写法中需要right-left == 1，这样right取不到，最终区间内就之后right一个元素。

二叉排序树

该专题有一个专门的blog，请移步blog：二叉排序树。

哈希表

标题
哈希表
时间限制
2 S
内存限制
10000 Kb
问题描述：
用除留余数法和线性探测再散列的冲突解决方法构造哈希表
输入：
输入数据第一行为两个正整数分别为：哈希表表长m（m<100）和除数p（p<=m）。后面每一行是一个整数关键字，以-1作为输入的结束。
输出：
若输入的关键字在哈希表中已存在，则输出该关键字在哈希表中的位置，继续等待输入下一个关键字。
若输入的关键字在哈希表中不存在，则判断当前哈希表中关键字的个数是否等于m-1，若相等，则输出“Table full”，程序结束；否则将关键字插入哈希表，并输出该关键字插入在哈希表中的位置，继续等待输入下一个关键字。

示例输入：
5 3
1
2
3
4
5
-1
示例输出：
1
2
0
3
Table full

#include<iostream>
#include<map>
using namespace std;
int hash[105];
int mode, table_size;
int key;
int value;
int now_size;
map<int, int>M;
void hash_search(int key)
{
 for (int i = 0; i < table_size; i++)
 {
  if (::hash[i] == key)
  {
   cout << i << "\n";
   return;
  }
 }
}
void hash_function(int key)
{
 value = key % mode;
 if (M[key])//一定要注意记录该元素是否在表中,否则就要使用逆着解决哈希冲突的方向查找元素,这里一旦发现该元素在表中直接遍历元素,降低程序了复杂度.
 {
  hash_search(key);
  return;
 }
 if (now_size == table_size - 1)
 {
  cout << "Table full\n";
  return;
 }
 while (::hash[value] != -1)
 {
  value = (value + 1)%table_size;
 }
 cout << value << "\n";
 ::hash[value] = key;
 M[key]++;
 now_size++;
}
int main()
{
 for (int i = 0; i <= 104; i++)
 {
  ::hash[i] = -1;
 }
 cin >> table_size >> mode;
 while (1)
 {
  cin >> key;
  if (key == -1)
  {
   break;
  }
  hash_function(key);
 }
 return 0;
}

无向连通子图

标题
求无向图连通子图
时间限制
2 S
内存限制
10000 Kb
问题描述
求无向图连通子图个数
问题输入
测试数据由m+1行构成，第一行为两个正整数n（1<n<=30）和m（1<m<100），分别表示顶点数（顶点编号为1,2,…,n）和边数，其后是m行数据，每行数据是一条边的信息，包括两个数字，分别表示该边关联的两个顶点。
问题输出
输出两行信息，第一行输出该图中连通子图的个数。第二行按照升序输出每个连通子图中顶点个数。
输入样例
9 8
1 2
1 3
2 4
3 4
5 7
5 6
6 7
8 9

输出样例
3
2 3 4

并查集+map记录出现的次数

#include<algorithm>
#include<map>
#include<iostream>
#include<iterator>
using namespace std;
map<int,int>M;
map<int,int>::iterator it;
int node_number,vertex_number;
int u,v,cnt;
int father[50];
int find_father(int x)
{
 while(x!=father[x])
 {
  x = father[x];
 }
 return x;
}
int main()
{
 cin>>node_number>>vertex_number;
 for(int i = 1;i<=node_number;i++)
 {
  father[i] = i;
 }
 for(int i = 1;i<=vertex_number;i++)
 {
  cin>>u>>v;
  father[v] = find_father(u);
 }
 for(int i = 1;i<=node_number;i++)
 {
  father[i] = find_father(father[i]);
  if(M[father[i]] == 0)
  {
   cnt++;
  }
  M[father[i]]++;
 }
 cout<<cnt<<endl;
 for(it = M.begin();it!=M.end();it++)
 {
  cout<<it->first<<" "<<M[it->first]<<endl;//在题目要求中不需要输出map的键 
  //这里的方法是对于迭代器使用的，不是map本身，请注意写法
 }
 return 0;
}

最小生成树

题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式
第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数 X_i,Y_i,Z_i,表示有一条长度为 Z_i
的无向边连接结点 X_i,Y_i。

输出格式
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例
输入 #1
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出 #1
7
说明/提示
数据规模：

对于 20\%20% 的数据，N≤5，M≤20。

对于 40\%40% 的数据，50N≤50，2500M≤2500。

对于 70\%70% 的数据，N≤500，4M≤10^4。

对于 100\%100% 的数据：1≤N≤5000,1≤M≤2×10^5。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int node_number,edge_number;
struct Vertex
{
 int u;
 int v;
 int w;
};
vector<Vertex>edge;
int father[5005];
int u,v,w,cnt,cost;
bool cmp(Vertex&a,Vertex&b)
{
 return a.w<b.w;
}
int find_father(int x)
{
 while(x!=father[x])
 {
  x = father[x];
 }
 return x;
}
void kruskal()
{
 int i;
 for(i = 0;i<edge_number;i++)
 {
  int u = edge[i].u;
  int v = edge[i].v;
  int w = edge[i].w;
  int u_father = find_father(u);
  int v_father = find_father(v);
  if(u_father == v_father)
  {
   continue;
  }
  father[v_father] = u_father;
  cost = cost+w;
  cnt++;
  if(cnt == node_number-1)
  {
   break;
  }
 }
 if(i>=edge_number)
 {
  cost = -1;
 }
}
int main()
{
 cin>>node_number>>edge_number;
 for(int i = 1;i<=node_number;i++)
 {
  father[i] = i;
 }
 Vertex temp;
 for(int i = 1;i<=edge_number;i++)
 {
  cin>>temp.u>>temp.v>>temp.w;
  edge.push_back(temp);
 }
 sort(edge.begin(),edge.end(),cmp);
 kruskal();
 if(cost!=-1)
 {
  cout<<cost<<endl;
 }
 else
 {
  cout<<"orz"<<endl;
 }
 return 0;
}

二叉排序树的建立和遍历

题目： 二叉排序树之父结点
问题描述
给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。
输入格式
测试数据有两行。第一行是一个数字N（N<=100），表示待插入的节点数。第二行是N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10^8。
输出格式
输出共N行，每次插入节点后，输出该节点对应的父亲节点的关键字值。
样例输入
5
2 5 1 3 4
样例输出
-1
2
2
5
3
样例说明
无。

#include<iostream>
using namespace std;
int sav = -1, node_number;
struct Node
{
 Node* left = NULL;
 Node* right = NULL;
 int value;
};
Node* head = NULL;
void insert_node(int value, Node*& head)//一定要加上引用，否则不能更改指针的指向。
{
 if (head == NULL)
 {
  head = new Node;
  head->value = value;
  cout << sav << endl;
 }
 else if (value < head->value)
 {
  sav = head->value;
  insert_node(value, head->left);
 }
 else if (value > head->value)
 {
  sav = head->value;
  insert_node(value, head->right);
 }
}
int main()
{
 cin >> node_number;
 int v;
 for (int i = 1; i <= node_number; i++)
 {
  cin >> v;
  insert_node(v, head);
 }
 return 0;
}

题目： 二叉排序树的遍历
问题描述
输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。
输入格式
输入第一行包括一个整数n(1<=n<=100)。
接下来的一行包括n个整数。
输出格式
将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。
每种遍历结果输出一行。每行最后一个数据之后有一个空格。
输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。
样例输入
5
1 6 5 9 8
样例输出
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1
样例说明
无。

#include<iostream>
#include<vector>
#include<iterator>
using namespace std;
struct Node
{
 int value;
 Node*left = NULL;
 Node* right = NULL;
};
int node_number;
Node*head = NULL;
vector<int>preorder;
vector<int>inorder;
vector<int>postorder;
vector<int>::iterator it;
void insert_node(int value,Node*&head)
{
 if(head == NULL)
 {
  head = new Node;
  head->value = value;
 }
 else if(value < head->value)
 {
  insert_node(value,head->left);
 }
 else if(value > head->value)
 {
  insert_node(value,head->right);
 }
}
void traverse(Node*aim)//注意遍历一定要专门写一个函数，不能在建树的时候遍历
{
 if(aim!=NULL)
 {
  preorder.push_back(aim->value);
  traverse(aim->left);
  inorder.push_back(aim->value);
  traverse(aim->right);
  postorder.push_back(aim->value);
 }
}
int main()
{
 cin>>node_number;
 int value;
 for(int i = 1;i<=node_number;i++)
 {
  cin>>value;
  insert_node(value,head);
 }
 traverse(head);
 for(it = preorder.begin();it!=preorder.end();it++)
 {
  cout<<(*it)<<" ";
 }
 cout<<"\n";
 for(it = inorder.begin();it!=inorder.end();it++)
 {
  cout<<(*it)<<" ";
 }
 cout<<"\n";
 for(it = postorder.begin();it!=postorder.end();it++)
 {
  cout<<(*it)<<" ";
 }
 cout<<"\n";
}

题目： 相同二叉排序树
问题描述
判断两序列是否为同一二叉排序树序列。
输入格式
数据有多组。每组数据第一行是一个数n，(1<=n<=20) 表示有n个需要判断，n=0 的时候输入结束。接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉排序树。接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉排序树。
输出格式
如果二叉排序树相同则输出YES，否则输出NO
样例输入
2
567432
543267
576342
0
样例输出
YES
NO
样例说明
无

1、建树，和上面两个题目相同。
2、比较。下面先贴出递归的比较的代码。可以根据返回值来确定两个树是否相同。

int compare(BiTree t1, BiTree t2)
{
    if (t1 == NULL && t2 == NULL)
    {
        return 1;
    }
    else if (t1 == NULL || t2 == NULL)
    {
        flag = 0;
        return 0;
    }
    else if (t1->data != t2->data)
    {
        flag = 0;
        return 0;
    }
    else
        return compare(t1->l, t2->l) && compare(t1->r, t2->r);
}

完整代码,比较啰嗦，只看上面的关键代码就可以。

#include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef struct node
{
    int data;
    struct node* l, * r;
}BiTode, * BiTree;
BiTree t1, t2;
int flag;
BiTree insert(BiTree t, int x)
{
    if (t == NULL)
    {
        t = (struct node*)malloc(sizeof(struct node));
        t->data = x;
        t->l = NULL;
        t->r = NULL;
    }
    else if (x < t->data)
    {
        t->l = insert(t->l, x);
    }
    else
    {
        t->r = insert(t->r, x);
    }
    return t;
}
BiTree creat(char a[], int n)
{
    int j = 0;
    BiTree t = NULL;
    while (j < n)
    {
        t = insert(t, a[j] - '0');
        j++;
    }
    return t;
}
int compare(BiTree t1, BiTree t2)
{
    if (t1 == NULL && t2 == NULL)
    {
        return 1;
    }
    else if (t1 == NULL || t2 == NULL)
    {
        flag = 0;
        return 0;
    }
    else if (t1->data != t2->data)
    {
        flag = 0;
        return 0;
    }
    else
        return compare(t1->l, t2->l) && compare(t1->r, t2->r);
}
int main()
{
    int n, len;
    char a[11], b[11];
    //while (scanf("%d", &n) != EOF && n)
    while(cin>>n&&n)
    {


        //scanf("%s", a);
        cin >> a;
        len = strlen(a);//strlen的参数只能是char 类型
        t1 = creat(a, len);
        while (n--)
        {
            //scanf("%s", b);
            cin >> b;
            t2 = creat(b, len);
            flag = 1;
            compare(t1, t2);
            if (flag == 1)
                printf("YES\n");
            else printf("NO\n");
        }
    }## 并查集+unique 判断无向连通子图的个数

高铁网络
描述：
国家建设高铁网络，网络由一些连接城市的高铁线路构成。现有高铁建设情况可列为一张统计表，表中列出了每一条高铁线路直接连接的两个城市。国家的建设目标是全国每两个城市之间都可以实现高铁交通（但不一定有直接的高铁线路相连，只要能间接通过高铁线路可达即可）。问最少还要建设多少条高铁线路？
输入说明：
测试用例的第1行给出两个正整数，分别是城市数目N(<1000)和现有高铁线路数目M。随后的M行对应M条高铁线路，每行给出一对正整数，分别是该条高铁线路直接连接的两个城市的编号。为简单起见，城市从1到N编号。
输出说明：
在一行上输出最少还需要建设多少条高铁线路。
输入样例：
9 8
1 2
1 3
2 4
3 4
5 7
5 6
6 7
8 9
输出样例：
2
实现提示：
该问题实质为求连通分量的个数减一，可用深度优先或广度优先搜索求解，也可用MFSet求解。

在unique之前一定要记得先sort。

```Bash
#include<iostream>
#include<algorithm>
using namespace std;
int city_number,road_number;
int father[1005];
int find_father(int x)
{
 while(x!=father[x])
 {
  x = father[x];
 }
 return x;
}
int main()
{
 cin>>city_number>>road_number;
 for(int i = 1;i<=city_number;i++)
 {
  father[i] = i;
 }
 int u,v;
 for(int i = 1;i<=road_number;i++)
 {
  cin>>u>>v;
  int u_father = find_father(u);
  int v_father = find_father(v);
  if(u_father!= v_father)
  {
   father[v_father] = u_father;
  }
 }
 for(int i = 1;i<=city_number;i++)
 {
  father[i] = find_father(father[i]);
 }
 sort(&father[1],&father[city_number+1]);
 int *tail = unique(&father[1],&father[city_number+1]);
 int number = tail-&father[1];
 number--;
 cout<<number<<endl;
 return 0;
}

关键路径

题目8：关键路径
问题描述
计算AOE-网中关键路径的长度。
输入格式
输入数据第一行是一个正整数，表示图中的顶点个数n（顶点将分别按0，1，…，n-1进行编号），顶点数不超过100，其中0为源点，n-1为汇点。之后的n行每行都包含n个整数，为AOE-网的邻接矩阵，其中0表示两个顶点间无直接可达的弧，大于0的整数表示活动持续的时间。
输出格式
输出AOE-网中关键路径的长度，如果网中有环，则输出“NO”。
样例输入
9
0 6 4 5 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 2 0 0 0
0 0 0 0 0 0 9 7 0
0 0 0 0 0 0 0 4 0
0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 0
样例输出
18

输出说明：如果网中有环，则示例输出如下：
NO

//拓扑序，最早开始时间
//逆拓扑序，最迟开始时间
//二者相等即为关键节点
//关键节点连接的路径即为关键路径

#include<cstdio>
#include<algorithm>
using namespace std;

const int INF = 1 << 31;

int n;
bool hav_cy = 0;
int G[110][110];//图的邻接表
int es[110];//每个节点的最早开始时间数组
int ls[110];//每个节点的最晚开始时间数组
bool used[110];//DFS的标记数组

void init() {
    fill(es, es + n, 0);
    fill(ls, ls + n, INF);
    fill(used, used + n, 0);
}

void find_es(int now) {
    if (now == n) return;
    //如果这个节点已经是图的最后一个节点，则结束DFS
    for (int i = 0; i < n; ++i) {//循环节点位置，寻找更新es的目标
        if (G[now][i]) {//如果now和i节点连通
            if (used[i]) {//如果在循环过程中找到了已经搜索过的节点，则这个图中存在环，DFS结束
                hav_cy = 1;
                return;
            }
            else {
                es[i] = max(es[i], es[now] + G[now][i]);
                //更新i项目的最晚开始时间，为所有在它之前的项目完成时间取最大值
                used[i] = true;//将i项目标记为已访问
                find_es(i);//i项目为DFS的下一个目标，进一步更新路径
                used[i] = false;//回溯
            }
        }
    }
}

void find_ls(int now) {
    if (now == -1) return;
    for (int i = 0; i < n; ++i) {
        if (G[i][now]) {
            ls[i] = min(ls[i], ls[now] - G[i][now]);
            find_ls(i);
        }
    }
}

int main() {
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &G[i][j]);
        }
    }
    find_es(0);
    if (hav_cy) {
        printf("NO\n");
        return 0;
    }
    else {
        fill(ls, ls + n, es[n - 1]);
        find_ls(n - 1);
    }
    printf("%d\n", es[n - 1]);
    return 0;
}

我自己的代码

#include<iostream>
#include<algorithm>
using namespace std;
int es[105],ls[105];
int node_number;
int map[105][105];
int has_cl = 0;
int vis[105];
void find_es(int x)
{
 if(x == node_number)
 {
  return;
 }
 for(int i = 0;i<node_number;i++)
 {
  if(map[x][i])
  {
   if(vis[i] == 1)
   {
    has_cl = 1;
    return;
   }
   else
   {
    es[i] = max(es[i],es[x]+map[x][i]);//将经过x点的路径长度和es[i]数组内的数据长度作比较 
    vis[i] = 1;
    find_es(i);
    vis[i] = 0;
   }
  }
 }
}
void find_ls(int x)
{
 if(x == -1)
 {
  return;
 }
 for(int i = 0;i<node_number;i++)
 {
  if(map[i][x])
  {
   if(vis[i] == 0)
   {
    ls[i] = min(ls[i],ls[x]-map[i][x]);
    vis[i] = 1;
    find_ls(i);
    vis[i] = 0;
   }
  }
 }
}
int main()
{
 cin>>node_number;
 for(int i = 0;i<node_number;i++)
 {
  for(int j = 0;j<node_number;j++)
  {
   cin>>map[i][j]; 
  }
 }
 find_es(0);
 if(has_cl == 1)
 {
  cout<<"NO"<<endl;
  return 0;
 }
 fill(&ls[0],&ls[node_number],es[node_number-1]);
 find_ls(node_number-1);
 cout<<ls[node_number-1]<<endl;
 return 0;
}

判断有向图中是否有环

题目：判断有向图中是否有环
问题描述
判断有向图中是否有环。
输入格式
输入数据第一行是一个正整数，表示n个有向图，其余数据分成n组，每组第一个为一个整数，表示图中的顶点个数n，顶点数不超过100，之后为有向图的邻接矩阵。
输出格式
输出结果为一行，如果有环，则输出1，如果无环，则输出0。按顺序输出这n个有向图的判断结果，前后结果的输出不加空格。
样例输入
3
2
0 1
0 0
3
0 1 1
0 0 0
0 0 0
4
0 1 0 0
0 0 0 1
0 0 0 1
1 0 0 0
样例输出
001

#include<iostream>
using namespace std;
int map[105][105];
int node_number;
int times;
int vis[105];
int has_cl;
void find_cl(int start)
{
 if(start == node_number)
 {
  return;
 }
 for(int i = 0;i<node_number;i++)
 {
  if(map[start][i])
  {
   if(vis[i])
   {
    has_cl = 1;
    return;
   }
   else
   {
    vis[i] = 1;
    find_cl(i);
    vis[i] = 0;
   }
  }
 }
}
int main()
{
 cin>>times;
 for(int i = 1;i<=times;i++)
 {
  has_cl = 0;
  cin>>node_number;
  for(int x = 0;x<node_number;x++)
  {
   for(int y = 0;y<node_number;y++)
   {
    cin>>map[x][y];
   }
  }
  for(int x = 0;x<node_number;x++)
  {
   find_cl(x);
  }
  if(has_cl)
  {
   cout<<"YES\n";
  }
  else
  {
   cout<<"NO\n";
  }
 }
}

图的广度优先遍历

题目：图的广度优先遍历
问题描述
已知无向图的邻接矩阵，以该矩阵为基础，给出广度优先搜索遍历序列，并且给出该无向图的连通分量的个数。在遍历时，当有多个点可选时，优先选择编号小的顶点。（即从顶点1开始进行遍历）
输入格式
第一行是1个正整数，为顶点个数n（n<100），顶点编号依次为1，2，…，n。后面是邻接矩阵，n行n列。
输出格式
共2行。第一行输出为无向图的广度优先搜索遍历序列，输出为顶点编号，顶点编号之间用空格隔开；第二行为无向图的连通分量的个数。
样例输入
6
0 1 0 0 0 0
1 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 1
0 0 0 0 1 0
样例输出
1 2 5 6 3 4
2

#include<iostream>
#include<queue>
using namespace std;
int map[105][105];
queue<int> que;
int node_number;
int record[105];
int cnt;
void BFS(int start, int color)
{
 int temp;
 que.push(start);
 record[start] = color;
 while (!que.empty())
 {
  temp = que.front();
  cout << temp << " ";
  que.pop();
  for (int i = 1; i <= node_number; i++)
  {
   if (map[temp][i]&&record[i] == 0)
   {
    record[i] = color;
    que.push(i);
   }
  }
 }
}
int main()
{
 cin >> node_number;
 for (int i = 1; i <= node_number; i++)
 {
  for (int j = 1; j <= node_number; j++)
  {
   cin >> map[i][j];
  }
 }
 for (int i = 1; i <= node_number; i++)
 {
  if (record[i] == 0)
  {
   BFS(i, ++cnt);
  }
 }
 cout << "\n" << cnt << "\n";
 return 0;
}

图的深度优先遍历

题目：图的深度优先遍历
问题描述
已知无向图的邻接矩阵，以该矩阵为基础，给出深度优先搜索遍历序列，并且给出该无向图的连通分量的个数。在遍历时，当有多个点可选时，优先选择编号小的顶点。（即从顶点1开始进行遍历）
输入格式
第一行是1个正整数，为顶点个数n（n<100），顶点编号依次为1，2，…，n。后面是邻接矩阵，n行n列。
输出格式
共2行。第一行输出为无向图的深度优先搜索遍历序列，输出为顶点编号，顶点编号之间用空格隔开；第二行为无向图的连通分量的个数。
样例输入
6
0 1 0 0 0 0
1 0 0 0 1 0
0 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 1
0 0 0 0 1 0
样例输出
1 2 5 6 3 4
2

#include<iostream>
using namespace std;
int map[105][105];
int node_number,cnt;
int record[105];
void DFS(int color,int now)
{
 if(now == node_number+1)
 {
  return;
 }
 record[now] = color;
 cout<<now<<" ";
 for(int i = 1;i<=node_number;i++)
 {
  if(map[now][i]&&record[i] == 0)
  {
   DFS(color,i);
  }
 }
}
int main()
{
 cin>>node_number;
 for(int i = 1;i<=node_number;i++)
 {
  for(int j = 1;j<=node_number;j++)
  {
   cin>>map[i][j];
  }
 }
 for(int i = 1;i<=node_number;i++)
 {
  if(record[i] == 0)
  {
   DFS(++cnt,i);
  }
 }
 cout<<"\n"<<cnt<<"\n";
 return 0;
}

单源最短路径

题目描述
给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。

数据保证你能从 ss 出发到任意点。

输入格式
第一行为三个正整数 n, m, sn,m,s。 第二行起 mm 行，每行三个非负整数 u_i, v_i, w_i，表示从 u_i到 v_i有一条权值为 w_i的有向边。

输出格式
输出一行 nn 个空格分隔的非负整数，表示 ss 到每个点的距离。

输入输出样例
输入 #1复制
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出 #1复制
0 2 4 3
说明/提示
样例解释请参考 数据随机的模板题。

1≤n≤10^5；
1≤m≤2×10^5;

#include<iostream>
#include<queue>
#include<functional>
#include<vector>
#include<algorithm>
#include<climits> 
using namespace std;
int edge_number,node_number,start;
struct Edge
{
 int cost;
 int to;
};
typedef pair<int,int> P;//pair在优先队列中是以first为关键字排序的
vector<P>edge[100005];//相当于用一个二维动态数组把所有以某个固定点为起点的边存在一起，便于遍历。
int dis[100005];
int vis[100005];//一定要有vis数组，否则会出现死循环，MLE。
priority_queue<P,vector<P>,greater<P> > que;
void DJ(int start)
{
 fill(&dis[1],&dis[node_number+1],INT_MAX);
 P elem;
 elem.first = 0;
 elem.second = start;
 dis[start] = 0;//不能忘记初始化start位置的dis，否则会导致图不连通，也不能在这里就修改start的vis,这将导致在进入while循环后直接被continue掉
 que.push(elem);
 int v,w;
 while(!que.empty())
 {
  elem = que.top();
  que.pop();
  w = elem.first;
  v = elem.second;
  if(vis[v])
  {
   continue;
  }
  vis[v] = 1;
  if(dis[v]<w)//别忘记加上这一句话，节省运行时间
  {
   continue;
  }
  int len = edge[v].size();
  P next;
  for(int i = 0;i<len;i++)
  {
   next.first = edge[v][i].first;
   next.second = edge[v][i].second;
   if(dis[next.second] > dis[v]+next.first)//是next的cost不是v的cost
   {
    dis[next.second] = dis[v]+next.first;
    next.first = dis[next.second];//入队列的是dis[next.second]而不是next.second的cost
    que.push(next);
   }
  }
 }
}
int main()
{
 int u,v,w;
 P temp;
 cin>>node_number>>edge_number>>start;
 for(int i = 1;i<=edge_number;i++)
 {
  cin>>u>>v>>w;
  temp.first = w;
  temp.second = v;
  edge[u].push_back(temp);
 }
 DJ(start);
 for(int i = 1;i<=node_number;i++)
 {
    if (dis[i] == INT_MAX)
    {
     dis[i] = 2e31 - 1;
    }
  cout<<dis[i]<<" ";
 }
 cout<<"\n";
 return 0;
}

多源最短路径

Floyd算法
将所有节点的距离都存在一个数组里，由于要枚举所有的两两组合以及每一个组合的“中转点”，再进行松弛操作
在使用前要对dis数组初始化为INT_MAX.

for(int k = 1;k<=vertexnum;k++>)
{
    for(int i = 1;i<=vertexnum;i++)
    {
        for(int j = 1;j<=vertexnum;j++)
        {
            dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);//松弛操作，即更新每两个点之间的距离
        }
    }
}

完全二叉树的子树

题目：完全二叉树的子树
问题描述
对一棵完全二叉树，采用自上而下、自左往右的方式从1开始编号，我们已知这个二叉树的最后一个结点是n，现在的问题是结点m所在的子树一共包括多少个结点？
输入格式
输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。0 0表示输入结束。
输出格式
对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。
样例输入
3 12
0 0
样例输出
4

若编号为i的结点有左孩子结点,则左孩子结点的编号为2i；若编号为i的结点有右孩子结点,则右孩子结点的编号为(2i+1)。
当2i>n，则结点i无左孩子，无左孩子则结点i为叶子结点；当2i+1>n，则结点无右孩子。

#include<iostream>
using namespace std;
int aim_node,node_number;
int cnt;
void find_child(int x)
{
 if(x > node_number||x<1>)//注意这里是两个条件，保证x在1~node_number之间即可
 {
  return;
 }
 cnt++;
 find_child(2*x);//左孩子是2*x而不是2*x-1，一个满二叉树的左右孩子的编号应该是相邻的
 find_child(2*x+1);
}
int main()
{
 while(1)
 {
  cnt = 0;
  cin>>aim_node>>node_number;
  if(aim_node==0&&node_number == 0)
  {
   break;
  }
  find_child(aim_node);
  cout<<cnt<<"\n";
 }
 return 0;
}

扩展先序转中序

题目：二叉树扩展先序遍历转中序遍历
问题描述
编一个程序，读入用户输入的一串扩展先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的扩展先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入格式
输入包括1行字符串，长度不超过100。
输出格式
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。每个输出结果占一行。
样例输入
abc##de#g##f###
样例输出
c b e g d f a
样例说明
根据给定的扩展先序遍历序列，建立对应的二叉树，然后对所得的二叉树进行中序遍历输出结果即可

#include<iostream>
using namespace std;
struct Node
{
 char value;
 Node*left = NULL;
 Node*right = NULL;
};
Node*head = NULL;
char input;
void set_tree(Node*&head)
{
 if(!(cin>>input))
 {
  head = NULL;
  return;
 }
 if(input == '#')
 {
  head = NULL;
  return;
 }
 head = new Node;
 head->value = input;
 set_tree(head->left);
 set_tree(head->right);
}
void inorder(Node*head)
{
 if(head == NULL)
 {
  return;
 }
 inorder(head->left);
 cout<<head->value;
 inorder(head->right);
}
int main()
{
 set_tree(head);
 inorder(head);
 return 0;
}

哈夫曼树

#include<stdio.h>
#include<queue>
#include<functional>
#include<vector>
using namespace std;

priority_queue<int,vector<int>,greater<int> >q;
int n,ans=0;
int main()
{
 scanf("%d",&n);
 while(n--)
 {
  int t;
  scanf("%d",&t);
  q.push(t);
 }
 while(1)
 {
  int a=q.top();
  q.pop();
  if(q.empty())
   break;
  int b=q.top();
  q.pop();
  ans+=a+b;
  q.push(a+b);
 }
 printf("%d\n",ans);
}

哈夫曼树的wpl就是所有非叶子结点的权之和
这样子就不用专门去求路径长度了
直接遍历一遍找出非叶子结点相加就好了