请描述一个求解下面问题的线性时间算法：给出图 G的邻接表，计算G的极大简单子图的邻接表，在输入中不假设平行边邻接出现

极大简单子图是指一个无向图G的子图，其中任意两个不同的顶点都不相邻，且再添加任意一个与该子图不相邻的顶点时，该子图就不再是简单图。下面给出一个求解这个问题的线性时间算法：

首先，我们可以通过 BFS 或 DFS 遍历整个图 G，获取每个节点的邻居节点，并将它们存入一个邻接表中。这个邻接表可以用一个哈希表实现，其中每个键对应一个节点，每个值是一个列表，包含该节点的所有邻居节点。该哈希表的构建时间复杂度为 O(E)，其中 E 是边数。

接下来，我们可以对于每个节点 u，将邻接表中与其相邻的节点 v 和 w 分为两类：相邻的点（v,w）或者不相邻的点（v,w）。然后，我们可以在邻接表中删除所有与 u 相邻的点（v,w），并将其它不相邻的点重新加入邻接表中。这个过程的时间复杂度为 O(D)，其中 D 是与 u 相邻的点的数量。

最后，我们将剩余的节点和它们的邻居节点构成的子图加入结果邻接表中。因为每个节点只会被遍历一次，所以总时间复杂度为 O(V+E)，其中 V 是节点数。

相关问题

设计算法求解有向无环图的所有拓扑序列。用C++写出代码

拓扑排序算法可以解决有向无环图（DAG）的拓扑排序问题，即对于一个 DAG，找到一种线性排序，使得对于任意一条有向边 (u, v)，结点 u 在排序结果中都出现在结点 v 的前面。

以下是基于 Kahn 算法的 C++ 代码实现：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 1e5 + 5;
vector<int> graph[MAXN]; // 存储图的邻接表
int inDegree[MAXN]; // 存储每个节点的入度

vector<vector<int>> allTopoSort(int n) {
    vector<vector<int>> res; // 存储所有拓扑序列的结果
    queue<int> q; // 存储入度为 0 的节点
    vector<int> topoOrder; // 存储当前的拓扑序列

    // 初始化入度为 0 的节点
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // BFS 搜索入度为 0 的节点
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);

        for (int v : graph[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 判断是否存在拓扑序列
    if (topoOrder.size() == n) {
        res.push_back(topoOrder);
    }

    // 枚举入度为 0 的节点，从图中删除它并递归求解
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            for (int v : graph[i]) {
                inDegree[v]++;
            }
            inDegree[i] = -1;
            vector<vector<int>> subRes = allTopoSort(n);
            for (vector<int>& subOrder : subRes) {
                subOrder.insert(subOrder.begin(), i);
                res.push_back(subOrder);
            }
            inDegree[i] = 0;
            for (int v : graph[i]) {
                inDegree[v]--;
            }
        }
    }

    return res;
}

int main() {
    int n, m;
    cin >> n >> m;

    // 读入有向图，构建邻接表并计算每个节点的入度
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        inDegree[v]++;
    }

    // 求解所有拓扑序列
    vector<vector<int>> res = allTopoSort(n);

    // 输出所有拓扑序列
    for (vector<int>& topoOrder : res) {
        for (int u : topoOrder) {
            cout << u << " ";
        }
        cout << endl;
    }

    return 0;
}

该算法的时间复杂度为 $\mathcal{O}(n \cdot n!)$，其中 $n$ 是节点数。

设g=(v,e)g=(v,e)是一带权重的源结点为s的有向图

设g=(v,e)是一带权重的源节点为s的有向图。
1. 有向图是由一组顶点v和一组有向边e组成的图结构。每条边e有一个起始节点和一个结束节点，且有一个权重值。有向图中的边是有方向的，即从起始节点指向结束节点。
2. 源节点s是有向图中的起始节点，从源节点可以通过边到达其他节点，但其他节点可能不一定能到达源节点。
3. 带权重的有向图表示在边上对连接两个节点的路径进行了加权。权重可以表示距离、成本、时间等概念。
4. 在有向图中，可以通过各种算法来解决一些问题，比如查找最短路径、寻找最小生成树等。
5. 有向图可以用邻接矩阵或邻接表来表示。邻接矩阵是一个二维数组，对于任意一对节点，若它们之间存在一条边，则在矩阵中对应位置的值表示边的权重；若不存在边，则对应位置的值为无穷大。邻接表是通过链表的形式，对每个顶点v建立一个链表，链表中包含从顶点v出发的边以及边的权重。
6. 在有向图中，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）等算法进行遍历。DFS以深度为优先，从源节点出发递归地访问其连通的节点；BFS以广度为优先，先访问源节点的所有邻接节点，然后再按顺序依次访问这些邻接节点所连通的节点。
7. 有向图中的路径可以通过不同的算法来求解，如Dijkstra算法和Floyd-Warshall算法。Dijkstra算法可以用于求解单源最短路径问题，通过不断更新最短路径并更新路径权重来找到源节点到其他所有节点的最短路径。Floyd-Warshall算法可以用于求解所有节点对之间的最短路径，通过动态规划的方式逐步更新路径权重来获得最短路径。
8. 有向图中还有一些特殊的拓扑性质和算法，如拓扑排序和关键路径算法。拓扑排序用于确定有向无环图中节点的一种线性顺序，使得对每对有向边(u,v)来说，节点u在排序中都出现在节点v之前。关键路径算法用于确定有向加权图中的关键路径，即图中经过的路径总权重最大的路径。
总之，带权重的源节点为s的有向图是一种有向图，其边上带有权重值，可以通过各种算法来解决路径和拓扑问题。