五、图

0x00 有向图的拓扑排序

给定一个n个点m条边的有向图，请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。

若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。

输入样例：

3 3（指3个点3条边）

1 2

2 3

1 3

输出样例：

1 2 3

版本一:bfs 不断删除入度为0的点

bool topsort(){
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i++){//将所有入度为0的入队
        if(!ind[i]) q[++tt] = i;//ind[i]表示节点i的入度
    }
    while(hh<=tt){
        int t = q[hh++];
        for(int i = h[t]; i!=-1; i = ne[i]){
            int j = e[i];
            ind[j]--;
            if(ind[j]==0) q[++tt] = j;
        }
    }
    return tt==n-1;//如果节点全部入队 说明无环
    //若返回true,则可输出拓扑序列，即入队顺序
    //for(int i = 0; i < n; i++) cout<<q[i]<<" ";
}
版本二:dfs 利用dfs序 按dfs序从大到小输出点

int dfstime = 0;//dfs序(即dfs过程中 搜索结束的时间)
vector<pair<int,int> > ans;
int st[N];// -1 表示搜索完毕 1表示该轮dfs还没结束
bool dfs(int u){//给出dfs序以及返回是否有环
    if(st[u]==-1) return false;//对于已经搜索完毕了点 无需搜 
    if(st[u]==1) return true;//因为该点在当前轮搜到过 而现在又来了 第二次到达 说明存在环
    st[u] = 1;//当前轮开始访问
    dfstime++;//时间+1 到达u
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(dfs(j)) return true;//邻接点存在环
    }
    st[u] = -1;//以u为起点的dfs访问完毕
    ans.push_back({-dfstime,u});//记录该点的退出时间(dfs序) 变为负数 方便从大到小排序
    return false;//不存在环
}
bool topsort_dfs(){
    for(int i = 1; i <= n; i++){
        if(st[i]!=-1){
            if(dfs(i)) return false;//发现该连通分量有环 拓扑失败
        }
    }
    sort(ans.begin(),ans.end());
    for(auto v : ans){
        cout<<v.second<<" ";
    }
    return true;
}
0x01 Dijkstra求最短路

给定一个n个点m条边的有向图, 请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

int g[N][N];//邻接矩阵
int d[N];//距离数组
bool st[N];//标记数组
int n,m;
int dijkstra(){
    memset(d,0x3f,sizeof d);//初始时每个点到起点距离为无穷
    d[1] = 0;//1为起点
    for(int i = 0; i < n; i++){
        int t = -1;//最小值点
        for(int j = 1; j <= n; j++){//寻找未加入最短路的距离最小的点(此处可用堆优化找最小值)
            if(!st[j]&&(t==-1||d[t]>d[j])) t = j;
        }
        st[t] = true;
        for(int j = 1; j <= n; j++){//用新加入的点更新其它点
            if(!st[j]&&d[j] > d[t] + g[t][j]) d[j] = d[t]+g[t][j];
        }
    }
    if(d[n] == 0x3f3f3f3f) return -1;
    else return d[n];
}
0x02 最小生成树

给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。输出最小生成树的权重之和

版本一: prim算法

const int INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
int d[N];//每个点距离生成树的距离
bool st[N];
int prim(){
    memset(d,0x3f,sizeof d);
    int res = 0;//最小生成树的权重之和
    for(int i = 0; i < n; i++){
        int t = -1;
        for(int j = 1; j <= n; j++)
            if(!st[j]&&(t==-1||d[t] > d[j])) t = j;
        if(i&&d[t]==INF) return -1;//说明不联通,则不存在
        st[t] = true;
        if(i) res += d[t];//纳入该边权重，除了起点
        for(int j = 1; j <= n; j++){
            if(!st[j]&&d[j] > g[t][j]) d[j] = g[t][j]; 
        }
    }
    return res;
}
版本二: Kruskal算法求最小生成树

struct Edge{//边集
    int a,b,w;
    bool operator < (const Edge &E) const{//按权重从小到大排序
        return w < E.w;
    }
}e[N];
int n,m;
int p[N/2];//并查集数组 若p[i]=j 则表示i的父节点为j
int find(int x){//并查集 寻找x的根
    if(x!=p[x]) p[x] = find(p[x]);//路径压缩版
    return p[x];
}
int kruskal(){
    sort(e,e+m);//把边按权重从小到大排序
    int res = 0,cnt = 0;//最小生成树的权重之和，选择的边数
    for(int i = 1; i <= n; i++) p[i] = i;//并查集初始化
    for(int i = 0; i < m; i++){//从小到大选边
        int x = find(e[i].a), y = find(e[i].b);
        if(x!=y){//若该条边不构成回路 则加入
            p[x] = y;
            cnt++;
            res += e[i].w;//纳入该边
        }
    }
    return cnt==n-1 ? res:0x3f3f3f3f;//最终要选够n-1条边
}
0x03 floyd求最短路

即求出所有点对的最短距离

int d[N][N];//任意两点间的最短距离
int n,m;
void floyd(){
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j= 1; j <= n; j++){
                d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
            }
        }
    }
}
0x0b n皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。(攻击范围为所在的行、列、正反对角线上)。

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

    int n,ans;//n皇后 
    void dfs(int u, auto &col,auto &gd, auto &rgd){
        if(u==n){//搜索完毕
            ans++;
            return;
        }
        for(int j = 0; j < n; j++){//枚举u行放在j列时
            if(!col[j]&&!gd[j-u+n]&&!rgd[u+j]){//列,对角,反对角不冲突时
                col[j] = gd[j-u+n] = rgd[u+j] = 1;//占用
                dfs(u+1,col,gd,rgd);//进入下一行搜索
                col[j] = gd[j-u+n] = rgd[u+j] = 0;//恢复现场
            }
        }
    }
    int totalNQueens(int len) {
        n = len;
        vector<bool> col(n),gd(2*n),rgd(2*n);//列 对角线 反对角线
        dfs(0,col,gd,rgd);//从第0行开始搜索
        return ans;
    }
0x0c 迷宫问题

给定一个 n×n 的二维数组，如下所示：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

}; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

数据保证至少存在一条从左上角走到右下角的路径。

对于上图则输出如下路径：

0 0

1 0

2 0

2 1

2 2

2 3

2 4

3 4

4 4

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
PII pre[N][N];//保存搜狗所过程中上一步的坐标
bool g[N][N];
int n;
void bfs(PII start){
    int dx[]={-1,0,1,0}, dy[]={0,1,0,-1};//四个方向
    queue<PII> q;
    q.push(start);
    memset(pre,-1,sizeof pre);//为-1表示此处还没搜过
    pre[n-1][n-1] = {n-1,n-1};
    while(q.size()){
        PII t = q.front();//当前位置
        q.pop();
        int tx = t.first, ty = t.second;
        for(int i = 0; i < 4; i++){//向四个方向探索下一步
            int x = tx + dx[i], y = ty + dy[i];
            if(x<0||x>=n||y<0||y>=n||g[x][y]||pre[x][y].first!=-1) continue;
            q.push({x,y}),pre[x][y] = {tx,ty};//保存该步信息
        }
    }
    PII end({0,0});
    while(true){
        int x = end.first, y = end.second;
        printf("%d %d\n",x,y);
        if(x==n-1&&y==n-1) break;
        end = pre[x][y];
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) scanf("%d",&g[i][j]);
    PII end({n-1,n-1});
    bfs(end);//逆着搜(从终点向起点搜) 方便输出路径
    return 0;
}