一天一道算法题——图

前些天做了好几道关于图的题，现在来个整理。

图的概念就不介绍了。

记u为起点，v为终点

最简单的存储方式：

vector<int> g[maxn];

在上面的vector里，如果正向建图，那么再输入的时候g[u].push_back(v);

如果反向建图，那么就是g[v].push_back(u);

以下是一个关于反向建图并dfs遍历的题目。

P3916 图的遍历

AC代码：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
#define maxn 100010
using namespace std;

int n, m, vis[maxn];
vector<int> g[maxn];

void dfs(int x,int d) {
    if (vis[x])return;
    vis[x] = d;
    for (int i = 0; i < g[x].size(); i++) {
        dfs(g[x][i], d);
    }
}

int main() {
    cin >> n >> m;
    int u, v;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        g[v].push_back(u);//反向建图
    }
    for (int i = n; i >= 1; i--)dfs(i, i);
    for (int i = 1; i <= n; i++)printf("%d ", vis[i]);
    return 0;
}

正向的思路很复杂，但用逆向思维思考的话，代码就会非常简单。

然后第二个示例，是当要求图的存储进行排序的情况。

struct edge {
    int u, v;//u起点，v终点
}tmp;
vector<int> e[100010];
vector<edge> s;
while (m--) {
    scanf("%d%d", &tmp.u, &tmp.v);
    s.push_back(tmp);
}
sort(s.begin(), s.end(), cmp);
for (int i = 0; i < s.size(); i++) {
    e[s[i].u].push_back(i);
}

情况稍微变的有点复杂，代码里的e同上个示例中的g，作用不变。但在排序（代码中假定是对每个相同的起点，按终点大小排列）的时候，需要建一个临时的vector s当存储。

相应的cmp

inline bool cmp(edge a, edge b) {
    if (a.v == b.v)return a.u < b.u;
    return a.v < b.v;
}

题目：P5318【深基18.例3】查找文献

接下来是拓扑排序

拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

(1) 选择一个入度为0的顶点并输出之；

(2) 从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

题目：P1113杂务

代码：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<queue>
using namespace std;
const int N = 10010;
queue<int> q;
bool e[N][N];
int n,ans,ti[N], mx[N], ru[N];

void topo() {
    for (int i = 1; i <= n; i++) {
        if (ru[i] == 0) {//将入度为0的顶点放进q里
            q.push(i);
            mx[i] = ti[i];
        }
    }
    while (!q.empty()) {
        int d = q.front();//前序工作时间已经加上的顶点
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (e[d][i]) {
                ru[i]--;
                if (ru[i] == 0)q.push(i);
                mx[i] = max(mx[i], mx[d] + ti[i]);
            }
        }
    }
    for (int i = 1; i <= n; i++)
        ans = max(ans, mx[i]);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        ti[a] = b;
        while (c != 0) {
            ru[a]++;//入度
            e[c][a] = true;//图的创立
            scanf("%d", &c);
        }
    }
    topo();//拓扑排序
    printf("%d", ans);
    return 0;
}