第一阶段（3月28日至正式开学）

教材：《挑战程序设计竞赛2：算法和数据结构》

第0部分：基本数据结构

向量

栈

链表

第一部分：排序

插入排序

冒泡排序

选择排序

希尔排序

归并排序：时间复杂度$O(n\log n)$

#include <iostream>
using namespace std;
#define MAX 500000
#define SENTIVITY 1000000000

int L[MAX/2+1],R[MAX/2+1];
int cnt;

void merge(int A[], int n, int left, int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;
    for (int i = 0; i < n1; ++i) L[i] = A[left + i];
    for (int j = 0; j < n2; ++j) R[j] = A[mid + j];//开辟两个独立数组，存储数据
    L[n1] = R[n2] = SENTIVITY;
    int i = 0, j = 0;
    for (int k = left; k < right; ++k){
        cnt++;
        if (L[i] <= R[j]){
            A[k] = L[i++];
        }else{
            A[k] = R[j++];
        }//数据按照大小依次插入
    }
}

void mergesort(int A[], int n, int left, int right){
    if (left+1 < right){
        int mid = (left + right)/2;
        mergesort(A, n, left, mid);//前半部分排序
        mergesort(A, n, mid, right);//后半部分排序
        merge(A, n, left, mid, right);//融合
    }
}

int main(){
    int A[MAX], n, i;
    cnt = 0;
    scanf("%d",&n);
    
    for(i = 0; i < n; ++i){
        scanf("%d",&A[i]);
    }
    
    mergesort(A, n, 0, n);
    
    for (i = 0; i < n; ++i){
        printf("%d",A[i]);
        printf(" ");
    }
    cout << endl;
    printf("%d", cnt);
    return 0;
}

快速排序：时间复杂度$O(n\log n)$

//分割算法


//快排算法
quickSort(A,p,r)
    if p<r
         q=partition(A,p,r)
         quicksort(A,p,q-1)
         quicksort(A,q+1,r)

STL的Algorithm库中使用的也是快速排序算法，但快速排序本身是一种不稳定的算法。

逆序数问题

（1）基于冒泡排序实现：简单但时间复杂度高$O(n^2)$;

（2）基于归并排序实现：用到分治策略，时间复杂度$O(n\log n)$;

最小成本排序问题（考虑到单次操作的权重）

第二部分：数

第八章：树

基本概念

根（root）：没有父结点的结点；
叶（leaf）：没有子结点的结点；
内部结点：既不是根，也不是叶的结点；
度（degree）：某一结点拥有的字结点的数目；
深度（depth）：从根到结点的路径长度；
有根二叉树：有根结点，且所有结点的度均不超过2；（根/左二叉树/右二叉树）

有根树的实现

在C++语言中，可以使用结构体表达（左子右兄弟表示法）

1 2	struct Node{int parent, left, right}; struct Node T[MAX];

利用递归求深度

void setDepth(int u, int p){
    D[u] = p;//给u结点设置为深度p（相当于设置一个起始结点）；
    if (T[u].r != NIL) setDepth(T(u).r, p);//右兄弟：结点深度一致；
    if (T[u].l != NIL) setDepth(T(u).l, p+1);//左子：结点深度加一；
}

二叉树的表达

结点用结构体表达

1
2
3

struct Node{
  int parent, left, right;
};

二叉树的输入

for (int i = 0; i < n; ++i){ //n表示所有结点的总数目
  scanf("%d %d %d", &v, &l, &r);
  T[v].left = l;//设置子结点
  T[v].right = r;
  if (l != NIL) T[l].parent = v;//设置父结点
  if (r != NIL) T[r].parent = v;
}

结点的深度利用递归方法求解（自顶向下）

void setDepth(int u, int p){
    if (u == NIL) return;//对于异常值，表示结束
    D[u] = p;//给u结点设置为深度p（相当于设置一个起始结点）；
    if (T[u].r != NIL) setDepth(T(u).right, p+1);//右子：结点深度加一；
    if (T[u].l != NIL) setDepth(T(u).left, p+1);//左子：结点深度加一；
}

二叉树的高度递归法求解（自底向上）

int setHeight(int u){
  int h1 = 0, h2 = 0;//初始化变量
  if (T[u].left != NIL)
    h1 = setHeight(T[u].left) + 1;//左结点的高度基础上加一
  if (T[u].left != NIL)
    h2 = setHeight(T[u].right) + 1;//右结点的高度基础上加一
  return max(h1, h2);
}

树的遍历

前序遍历：根节点、左子树、右子树的顺序输出

void preParse(int u){
  if (u == NIL) return;
  printf("%d", u);
  preParse(T[u].left);
  preParse(T[u].right);
}

中序遍历：左子树、根节点、右子树的顺序输出

void inorder(int u){
  if (u == NIL) return;
  inorder(T[u].left);
  printf("%d", u);
  inorder(T[u].right);
}

后序遍历：左子树、右子树、根节点的顺序输出

void postorder(int u){
  if (u == NIL) return;
  postorder(T[u].left);
  postorder(T[u].right);
  printf("%d", u);
}

问题：根据前序遍历和中序遍历的结果重建树

前序遍历的第一个元素为根结点，找到其在中序遍历中的位置，分离出左右子树，之后做递归处理；

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

int n, pos;
vector<int> pre, in, post;//用来存储前序遍历、中序遍历、后序遍历的结果

//利用递归的思想处理左右子树
void rec(int l, int r){
  if (l >= r) return;
  int root = pre[pos++];
  //利用find函数在inorder中找到根结点，之后分割出左右子树
  int m = distance(in.begin(), find(in.begin(), in.end(), root));
  rec(l, m); //处理左子树
  rec(m + 1, r); //处理右子树
  post.push_back(root);
}

//将处理好后的后序遍历输出
void solve(){
  pos = 0;
  rec(0, pre.size());
  for (int i = 0; i < n; ++i){
    if (i) printf(" ");
    printf("%d", post[i]);
  }
  printf("/n");
}

int main(){
  scanf("%d", &n);
  //输入前序遍历数据
  for (int i = 0; i < n; ++i){
    int k;
    scanf("%d", &k);
    pre.push_back(k);
  }
  //输入中序遍历数据
  for (int j = 0; j < n; ++j){
    int m;
    scanf("%d", &m);
    in.push_back(m);
  }
  //输出后序遍历结果
  solve();
  return 0;
}

1
2
3

事实上，只要知道其中任意两种遍历结果，皆可重建第三种遍历结果；
（1）已知中序，后序：后序的最后一个结点为根结点——在中序中可以分为左子树、右子树，从而递归处理；
（2）已知前序遍历和后序遍历，无法唯一确定中序遍历；

第九章：二叉搜索树（使用指针）

设$x$为二叉搜索树的结点。如果$y$为$x$左子树中的结点，$z$为$x$右子树中的结点，则有$y\le x\le z$。如果对二叉搜索树做中序遍历，会得到一个升序的键值序列。（类似于二分法）

使用二叉树存储数据相对于使用列表时间复杂度更低，但实际结构较为复杂。

二叉搜索树的结点

struct Node{
  int key;//此处结点的键值
  Node *parent, *left, *right;//指向父结点与子结点
};

插入

从根开始，比较键值大小，大的向右搜索，小的向左搜索，从而找到空结点拓宽；时间复杂度$O(h)=O(\log n)$.

#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>

struct Node{
  int key;
  int *parent, *left, *right;
};//设置结点变量

Node *root, *NIL;

void insert(int k){//插入操作
  Node *y = NIL;
  Node *x = root;
  Node *z;
  //初始化Z变量，用于临时存储
  z = (Node *)malloc(sizeof(Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  //通过x变量循环寻找合适的位置
  while(x != NIL){
    y = x;
    if (z->key < x->key){
      x = x->left;
    }else{
      x = x->right;
    }
  }
  //y变量用于作为z所在的父结点
  z->parent = y;
  if (y == NIL){
    root = z;//判断z是否是第一个结点
  }else{
    if (z->key < y->key){
      y->left = z;
    }else{
      y->right = z;
    }
  }
}
//中序遍历函数
void inorder(Node *u){
  if (u = NIL) return;
  inorder(u->left);
  printf("%d", u->key);
  inorder(u->right);
}
//前序遍历函数
void preorder(Node *u){
  if (u == NIL) return;
  printf("%d", u->key);
  preorder(u->left);
  preorder(u->right);
}
//主函数
int main(){
  int n;
  scanf("%d", &n);
  
  string com;
  
  for(int i = 0; i < n; ++i){
    cin >> com;
    if (com = "insert"){//判断操作；输入
      scanf("%d", &x);
      insert(x);
    }else if(com = "print"){//判断操作：输出
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  
  return 0;
}

搜索：时间复杂度$O(h)=O(\log n)$.

Node * find(Node *u, int k){//在u为根节点的这棵树中寻找k是否存在
  while(u != NIL && k != u->key){ //u非空且未找到k值
    if (k < u->key) u = u->left;
    else u = u->right;
  }
  return u;
}

删除：时间复杂度$O(h)=O(\log n)$。难点在于，删除后如何保证二叉树的基本性质。

一共有三种情况需要考虑：无结点、一结点、两结点

（1）$z$没有子结点，需要删除其父结点的子结点；

（2）$z$拥有一个子结点时，将其父结点的子结点更新为该子结点，同时该子结点变换为父结点；

（3）$z$有两个子结点时，将$z$的后一个结点$y$的键值复制到$z$，然后删除$y$。注意，此处的“后一个结点”指的是中序遍历时排在后面的那一个结点。

//找到树中最小的元素
Node * treeMinimum(Node *x){
  while(x->left != NIL) x = x->left;
  return x;
}
//计算后一个结点的算法
Node * treeSuccessor(Node *x){
  //存在右子树时，最小值即是需删除的结点
  if (x->right != NIL) 
    return treeMinimum(x->right);
  //不存在右子结点时，要向上查询
  Node *y = x->parent;
  while(y != NIL && x == y->right){//当查到为右子树时才为后一个结点
    x = y;
    y = y->parent;
  }
  return y;
}

void treedelete(Node *z){
  Node *y;//删除的对象
  Node *x;//y的子结点
  
  //确定删除的结点
  //无结点或者只有一个结点时，y就是需要删除的对象
  if(z->left == NIL || z->right == NIL) y = z;
  //有两个结点时
  else y = treeSuccessor(z);
  
  //确定y的子结点x
  if (y -> left != NIL){
    x = y->left;
  }else{
    x = y->right;
  }
  
  if (x != NIL){
    x->parent = y->parent;
  }
  
  if (y->parent = NIL){//如果删除的是根结点
    root = x;
  }else{
    if (y == y->parent->left){//判断是左结点还是右结点
      y->parent->left = x;
    }else{
      y->parent->right = x;
    }
  }
  
  if (y != z){
    z->key = y->key;
  }
  
  free(y);
}

使用STL标准库管理集合

（1）序列式容器：新添加的元素置于特定位置，如vector, list两种。

（2）关联式容器：依据特定的排序标准来确定存储位置。其中，set由二叉搜索树实现，能够保持搜索、插入、删除的时间复杂度为$O(\log n)$；map也是基于平衡二叉搜索树实现，但存储方式不同。

1.set：根据元素值进行排序的集合，元素唯一不重复；可使用迭代器顺次访问各元素。需事先声明#include<set>; 初始化变量操作举例 set<int> S;
size()  返回set中元素个数； 
clear() 清空整个set；
begin() 指向set开头的迭代器； 
end()   指向set末尾的迭代器；
insert(key)  插入元素key;
erase(key)   删除元素key;
find(key)    查询元素key,如果有相同的则返回该元素的迭代器，否则指向末尾end();


2.map：每个元素拥有一个键与值，集合以键作为排序标准。元素唯一不重复，可用于实现“从字符串中删除字符串”这一类字典功能；需事先声明#include<map>，初始化举例map<string,int> T;
size() 返回map中的元素个数；
clear() 清除map中所有元素；
begin() 返回指向map开头的迭代器；
end() 返回指向map末尾的迭代器；
insert((key,val)) 插入元素（key,val），分别指代具体存储内容和相对应赋予的值。
erase(key) 删除值为key的元素；
find(key)  查询元素key,如果有相同的则返回该元素的迭代器，否则指向末尾end();

第十章：堆

（1）完全二叉树；所有叶结点深度相同，且所有内部结点都有两个子结点；

（2）近似完全二叉树：叶深度最大差距为1，最下层叶结点位于最左边的若干位置上；

（3）对于存储$n$个元素的完全二叉树，其树高为$\log_2 n$；

二叉堆：
（1）逻辑结构为完全二叉树，但事实上用一位数组存储数据，通过下标进行管理
（2）对于下标为i的结点——父结点：i/2；左结点：2i；右结点：2i+1；
（3）最大堆：结点的键值小于父结点的键值；最小堆：结点的键值小于父结点的键值；

代码：生成最大堆（时间复杂度$O(H)$）

#include <iostream>
using namespace std;
#define MAX 2000000

int H, A[MAX+1];//H是数组长度，A代表数组。（对于未知长度数组可以使用vector）

void maxHeapify(int i){
  int l, r, largest;
  l = 2 * i;//左结点
  r = 2 * i + 1;//右结点
  
  //找出左右结点中较大的一个
  if (l <= H && A[l] > A[i]) largest = l;
  else largest = i;
  if (l <= H && A[r] > A[largest]) largest = r;
  
  //将当前结点与较大的一个交换，同时循环进行；
  if (largest != i){
    swap(A[i], A[largest]);//交换两个函数的值
    maxHeapify(largest);
  }
}

int main(){
  scanf("%d", &H);
  for (int i = 1; i <= H; ++i) scanf("%d", &A[i]);
  for (int i = H/2; i >= i; --i) maxHeapify(i);//以2/H为起点，1位终点，自底向上交换
  for (int i = 1; i <= H; ++i) printf("%d", A[i]);
  printf("\n");
  return 0;
}

从底层开始对某一结点做最大堆处理，之后遍历全体。

优先级队列：优先取出最大键值的队列

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 2000000//数组最大长度
#define INFTY(1 << 32)//（复习一下位运算）

int H, A[MAX + 1];

void maxHeapify(int i){
  //参见上一小节
}

//删除最大键值的操作
int extract(){
  int maxv;
  if (H < 1) return -INFTY;//特殊情况，队列为0时无法删除
  maxv = A[1];
  A[1] = A[H];//最小元素放在最前方
  H--;//队列长度减一
  maxHeapify(1);//重新生成最大堆
  return maxv;
}

void increaseKey(int i, int key){
  if (key < A[i]) return;
  A[i] = key;
  while(i > 1 && A[i/2] < A[i]){
    swap(A[i], A[i/2]);
    i = i/2;
  }
}

void insert(int key){
  H++;
  A[H] = -INFTY;
  increaseKey(H, key);
  //把元素添加至末尾后，在自底向上循环判断其应所处位置
}

使用STL库实现优先级队列：priority_queue

（1）push()：向队列中插入一个元素；
（2）top(): 访问队列中的开头元素；
（3）pop(): 用于删除队列中的开头元素；
值得说明的是，在priority_queue中，开头元素永远是拥有最大优先级的元素；优先级可以由程序员确定，但默认int型数据中最大的元素优先级最高。

第十一章：动态规划法

基本概念：对已有的计算结果记忆化，方便直接调用，避免重复计算；用空间换取时间的策略；

例子：斐波拉契数列：使用数组存储每一次的计算结果

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    vector<long long int> F;
    F.push_back(1);
    F.push_back(1);
    for (int i = 2; i <= n; ++i){
        F.push_back(F[i-1]+F[i-2]);
    }
    printf("%lld", F[n]);
    return 0;
}

例子：求最长公共子序列

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
static const int N = 1000;

int lcs(string X, string Y){
    int c[N+1][N+1];//开辟二维数组计算已有计算结构
    int m = X.size();
    int n = Y.size();//计算给定序列的长度
    int maxl = 0;//初始化结果
    X = ' ' + X;
    Y = ' ' + Y;//为处理方便，在0位置上插入一个空位
    for (int i = 0; i <= m; ++i) c[i][0] = 0;
    for (int j = 0; j <= n; ++j) c[0][j] = 0;
    
    for (int i = 0; i <= n; ++i){
        for (int j = 0; j <= m; ++j){
            if (X[i] == Y[j]) c[i][j] = c[i-1][j-1] + 1;
            else c[i][j] = max(c[i][j-1], c[i-1][j]);
            maxl = max(maxl, c[i][j]);//更新答案
        }
    }
    return maxl;
}

int main(){
    int n;
    scanf("%d", &n);
    string X, Y;
    for (int i = 0; i < n; ++i){
        cin >> X >> Y;
        printf("%d", lcs(X,Y));
    }
    return 0;
}

数学解释

求解最大公共子序列可以分解为子问题：在长度较短的序列上加上一段序列再做判断；

（1）若两条序列中有一条为0，则此时的公共子序列为0；

（2）若两条序列中新加入的元素相等，那最大子序列则可以在$c[i-1][j-1]$的基础上加一；

（3）若二者不想等，则考虑取$\max(c[i-1][j], c[i][j-1])$;

对X和Y都做了循环，时间复杂度为$O(nm)$，由于开辟了数组，空间复杂度为$O(nm)$；

矩阵链乘法：时间复杂度$O(n^3)$

对于给定长度为$n$的矩阵链，若想得到其相乘结果，求最少的标量乘法计算次数；

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

static const int N = 100;

int main(){
    int n, p[N+1], m[N+1][N+1];
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i){
        scanf("%d%d", &p[i-1], &p[i]);//存入行、列数目
    }
    //m[i][j]表示从第i个矩阵乘至第j个矩阵的成本，那么在j小于i的情形下的结果不予j考虑；
    for (int i = 0; i <= n; ++i) m[i][i] = 0;
    //对于i,j相等的情况，实际上并没有进行计算
    for (int l = 2; l <= n; ++l){//l表示用于计算的矩阵的个数，从而控制i,j所在的范围
        for (int i = 1; i <= n - l + 1; ++i){
            int j = i + l - 1;
            m[i][j] = (1 << 21);
            for (int k = i; k <= j - 1; ++k){
                m[i][j] = min(m[i][j],m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]);
            }
        }
    }
    printf("%d", m[1][n]);
    return 0;
}

$m[i][j]$的最小成本就是$m[i][k],m[k+1][j]$的成本加上这两个矩阵的成本，其中$k$是位于$i,j$中的某一数值，可以与$i$相等，但不可以与$j$相等；对$i,j$中所有满足的元素进行遍历，最终求的最小值；但关于$i$和$j$的范围需要控制的；

第十二章：图

图的组成：结点（Node）、关系（Edge）；

图的分类：无向图、有向图、加权无向图、加权有向图；

图的基本算法：深度优先搜索、广度优先搜索；

图的表示

（1）领接表

每一个顶点对应一个表，表内存储相邻的点编号；

（2）领接矩阵

设二维数组为$M$，则$M[i][j]$表示顶点$i$和顶点$j$之间的关系；邻接矩阵呈现右上左下对称形式；

邻接矩阵可以直接引用边，但需要较大的内存空间且只能记录两个顶点间的一个关系；

深度优先搜索

基本思路：尽可能访问相邻顶点，进行递归搜索，搜索完毕后返回至另一相邻点，直至所有顶点都被搜索完毕；

方法一：递归

#include <iostream>
#include <stack>
using namespace std;
static const int N = 100;
static const int WHITE = 0;//白色表示为搜索过
static const int GRAY = 1;//灰色表示搜索状态中
static const int BLACK = 2;//黑色表示搜索完成

int n, M[N][N];
int color[N], d[N], f[N], tt;//color用于存储状态，d,f用于存储开始和结束时刻，tt为时钟
int nt[N];

//用递归的方法实现深度优先搜索，时间复杂度更高
void dfs_visit(int u){
  int v;
  color[u] = GRAY;//当前结点状态改变
  d[u] = ++tt;//记录访问时刻
  for (v = 0; v < n; ++v){ //对周边结点进行搜索
    if (M[u][v] == 0) continue; //若没有边，则不许搜索
    if (color[r] == WHITE) dfs_visit(v); //深度搜索
  }
  color[u] = black;
  f[u] = ++tt;
}

void dfs(){
    //对状态进行初始化
    for (int i = 0; i < n; ++i){
      color[i] = WHITE; 
      nt[i] = 0;
    }
    tt = 0;
    
    for (int u = 0; u < n; ++u){
      if (color[u] == WHITE) dfs_visit(u);
    }
    for (int i = 0; i < n; ++i){
      cout << i + 1 << " " << d[i] << " " << f[i] << endl;
    }
 }
  
int main(){
    int u, k, v;
    scanf("%d", &n);
    //对矩阵进行初始化
    for (int i = 0; i < n; ++i){
      for (int j = 0; j < n; ++j){
        M[i][j] = 0;
      }
    }
    //将图结构中的边用邻接矩阵存储
    for (int i = 0; i < n; ++i){
      scanf("%d%d", &u, &k);
      u--;//以0为起点的修正
      for(int j = 0; j < k; ++j){
        scanf("%d", v);
        v--;//0起点修正
        M[u][v] = 1;
      }
    }
    dfs();
    return 0;
}
//0起点修正：顶点从1开始，但计算机数组的存储从0开始，故减去1即可；

方法二：使用栈

1.将最初访问的顶点压入栈中；
2.若栈非空，则访问栈顶，之后若移动至另一点时再压入栈中，如不存在未访问结点，则结束搜索；

//用栈实现深度优先搜索，时间复杂度更低

//寻找相邻结点的函数
int next(int u){
  //判断是否存在一个结点
  for (int v = nt[u]; v < n; ++v){
    nt[u] = v + 1;
    if (M[u][v]) return v;
  }
  return -1;
}
//深度优先搜索函数
void dfs_visit(int r){
  for (int i = 0; i < n; ++i) nt[i] = 0;
  
  stack<int> S;
  S.push(r);//将当前结点压入栈中
  color[r] = GRAY;
  d[r] = ++tt;
  
  while(!S.empty()){
    int u = S.top();
    int v = next(u);
    if (v != -1){
      if(color[r] == WHITE){
        color[r] = GRAY;
        d[v] = ++tt;//记录开始访问时刻
        S.push(v);
      }else{
        S.pop();
        color[u] = BLACK;
        f[u] = ++tt;//记录结束访问时刻
      }
    }
  }
}

广度优先搜索（从起点开始，按照与起点的距离管理）

1.将起点s放入队列Q中

2.只要Q不为空，则循环：从Q中取出顶点进行访问，将与u相邻的未访问结点放入Q中，更新距离

缺点，广度优先搜索中，程序要调查每个顶点是否与其他所有结点相邻，故算法复杂度较高

#include <iostream>
#include <queue>
using namespace std;
static const int N = 100;
static const int INFTY = (1<<21);

int n, M[N][N];//顶点数目与图结构
int d[N];//距离

//从起点开始进行访问，度量与起点的距离
void bfs(int s){
  queue<int> q;
  q.push(s);
  for (int i = 0; i < n; ++i) d[i] = INFTY;//初始化，未判断前，均为无穷远
  d[s] = 0;
  int u;
  while(!q.empty()){
    u = q.front(); 
    q.pop();
    for (int v = 0; v < n; ++v){
      if (M[u][v] == 0) continue;
      if (d[v] != INFTY) continue;//d[v]不为无穷时，说明已经访问过并放入了栈中
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
  for (int i = 0; i < n; ++i){
    cout << i+1 << " "<<  ((d[i] == INFTY) ? (-1) : d[i]) << endl;
  }
}

int main(){
  int u, k, v;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i){
    for (int j = 0; j < n; ++j){
      M[i][j] = 0;
    }
  }
  
  for (int i = 0; i < n; ++i){
    scanf("%d%d", &u, &k);
    u--;
    for (int j = 0; j < k; ++j){
      scanf("%d", &v);
      v--;
      M[u][v] = 1;
    }
  }
  
  bfs(0);
  return 0;
}

连通分量问题（ALDS1_11_D）：利用广度优先搜索测量距离，只要距离不是无穷，则说明可以到达。

//思路，使用bfs
#include <iostream>
#include <queue>
using namespace std;
static const int N = 100000;
static const int INFTY = (1 << 21);

int n, m, q, M[N][N];
int d[N];

void bfs(int s){
  queue<int> q;
  q.push(s);
  for (int i = 0; i < n; ++i) d[i] = INFTY;
  d[s] = 0;
  int u;
  while(!q.empty()){
    u = q.front();
    q.pop();
    for (int v = 0; v < n; ++v){
      if (M[u][v] == 0) continue;
      if (d[v] != INFTY) continue;
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
}

int main(){
  scanf("%d%d", &n, &m);
  //初始化
  for (int i = 0; i < n; ++i){
    for (int j = 0; j < n; ++j){
      M[i][j] = 0;
    }
  }
  //存入图结构
  for (int i = 0; i < m; ++i){
    int u, v;
    scanf("%d%d", &u, &v);
    u--;
    v--;
    M[u][v] = 1;
  }

  scanf("%d", &q);
  for (int i = 0; i < q; ++i){
    int u, v;
    scanf("%d%d", &u, &v);
    u--;
    v--;
    bfs(u);
    if(d[v] != INFTY) cout << "yes" << endl;
    else cout << "no" << endl;
  }
  return 0;
}

但由于此题目中的顶点数量过大，故不宜使用邻接矩阵，而采用vector距离邻接表

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
static const int N = 100000;
static const int NIL = -1;

int n;
vector<int> G[MAX];
int color[MAX];

void dfs(int r, int c){
  stack<int> S;
  S.push(r);
  color[r] = c;
  while(!S.empty()){
    int u = S.top();
    s.pop();
    for (int i = 0; i < G[u].size(); ++i){
      int v = G[u][i];
      //如果还没有上色，就上色并以此作为结点继续上色
      if (color[v] == NIL){
        color[v] = c;
        S.push(v);
      }
    }
  }
}

void assignColor(){
  int id = 1;
  for (int i = 0; i < n; ++i) color[i] = NIL;
  for (int u = 0; u < n; ++i){
    if (color[u] == NIL) dfs(u, id++);
    //以u为起点展开深度优先搜索，并存储颜色，这样可以保持同一棵连通图
  }
}

int main(){
  int s, t, m, q;
  scanf("%d%d", n, m);
  //将关系存入邻接表
  for (int i = 0; i < m; ++i){
    scanf("%d%d", &s, &t);
    G[s].push_back(t);
    G[t].push_back(s);
  }
  
  assignColor();
  scanf("%d", &q);
  
  for (int i = 0; i < q; ++i){
    scanf("%d%d", &s, &t);
    if (color[s] == color[t]) cout << "yes" << endl;
    else cout << "no" << endl;
  }
  return 0;
}

第十三章：加权图

基本概念

（1）树：没有环的图；

（2）图G的生成树：图G的子图，包含了G的所有顶点，在保证是树的前提上保留尽量多的边；

（3）最小生成树：各边权重值最小的树；

（4）最短路径：给定顶点$s,d$之间各边权值最小的路径；

1 2	(1)单源最短路径：求给定顶点到其它所有顶点的最短路径； (2)全点对间最短路径：求“每一对顶点”之间的最短路径；

（5）最短路径生成树：给定顶点$s$，包含$s$到图$G$所有顶点最短路径的生成树；

最小生成树

数据结构与算法