请用c++写一个Tarjan算法

### 回答1：

我可以用C给你写一个Tarjan算法，它是一种用于图算法的深度优先搜索（DFS）算法，可以用来检测图中的强连通分量（SCC），并找出给定图的最小桥（给定两个节点之间的最小边）。具体的实现可以参考下面的代码：// Tarjan算法
// 参数:
// g: 图
// v: 从图中获取节点
// adj: 从节点获取邻接顶点
// t: 时间戳
// scc: 强连通分量
// stack: 栈
int tarjan(Graph &g, int v, std::vector<std::vector<int>> &adj, int t, std::vector<std::vector<int>> &scc, std::vector<int> &stack) {
// 设置节点v的时间戳
g.timestamp[v] = t;
// 设置节点v的最小时间戳
g.min_timestamp[v] = t;
// 将节点v加入栈中
stack.push_back(v);
// 对节点v的每一个邻接顶点w进行搜索
for (int w : adj[v]) {
if (g.timestamp[w] == -1) {
// 如果顶点w的时间戳未被设置，则递归搜索
tarjan(g, w, adj, t+1, scc, stack);
// 设置节点v的最小时间戳
g.min_timestamp[v] = std::min(g.min_timestamp[v], g.min_timestamp[w]);
} else if (std::find(stack.begin(), stack.end(), w) != stack.end()) {
// 如果顶点w已经在栈中，则设置节点v的最小时间戳
g.min_timestamp[v] = std::min(g.min_timestamp[v], g.timestamp[w]);
}
}
// 如果节点v的最小时间戳等于其时间戳，说明搜索结束
if (g.min_timestamp[v] == g.timestamp[v]) {
// 将节点v以及其之前的节点加入一个强连通分量
std::vector<int> component;
int w;
do {
w = stack.back();
stack.pop_back();
component.push_back(w);
} while (w != v);
scc.push_back(component);
}
return 0;
}

### 回答2：
Tarjan算法是一种用于在有向图中查找强连通分量（Strongly Connected Component，简称SCC）的算法。以下是用C语言实现的Tarjan算法的代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX 100

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Stack {
    int top;
    int array[MAX_VERTEX];
} Stack;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void addEdge(Node* graph[], int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph[src];
    graph[src] = newNode;
}

void DFS(int u, int disc[], int low[], int stackMember[], Stack* stack, Node* graph[], int* count) {
    static int time = 0;
    disc[u] = low[u] = ++time;
    stack->array[++stack->top] = u;
    stackMember[u] = 1;

    Node* i;
    for (i = graph[u]; i != NULL; i = i->next) {
        int v = i->data;
        if (disc[v] == -1) {
            DFS(v, disc, low, stackMember, stack, graph, count);
            low[u] = (low[u] < low[v]) ? low[u] : low[v];
        }
        else if (stackMember[v] == 1) {
            low[u] = (low[u] < disc[v]) ? low[u] : disc[v];
        }
    }

    int popVertex = 0;
    if (low[u] == disc[u]) {
        while (stack->array[stack->top] != u) {
            popVertex = stack->array[stack->top];
            printf("%d ", popVertex);
            stackMember[popVertex] = 0;
            stack->top--;
            (*count)++;
        }
        popVertex = stack->array[stack->top--];
        printf("%d\n", popVertex);
        stackMember[popVertex] = 0;
        (*count)++;
    }
}

void tarjanSCC(int vertices, Node* graph[]) {
    int disc[MAX_VERTEX], low[MAX_VERTEX], stackMember[MAX_VERTEX], count = 0;
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = -1;

    for (int i = 0; i < vertices; i++) {
        disc[i] = -1;
        low[i] = -1;
        stackMember[i] = 0;
    }

    for (int i = 0; i < vertices; i++) {
        if (disc[i] == -1) {
            DFS(i, disc, low, stackMember, stack, graph, &count);
        }
    }

    free(stack);
}

int main() {
    int vertices = 8;
    Node* graph[MAX_VERTEX];
    for (int i = 0; i < MAX_VERTEX; i++) {
        graph[i] = NULL;
    }
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 5);
    addEdge(graph, 5, 3);
    addEdge(graph, 5, 6);
    addEdge(graph, 6, 7);

    printf("Strongly Connected Components:\n");
    tarjanSCC(vertices, graph);

    return 0;
}

以上是一个使用C语言编写的Tarjan算法的示例代码。该代码首先定义了节点和栈的数据结构，然后实现了创建节点和添加边的函数。在Tarjan算法函数中，使用DFS进行遍历，并将每个节点的发现时间和最低发现时间进行更新，从而找到强连通分量。最后，打印出所有的强连通分量。

注意：以上代码仅为示例，实际使用中可能需要根据具体情况进行调整和优化。

### 回答3：
Tarjan算法是一种常见的图算法，用于查找图中的强连通分量。以下是一个用C语言写的Tarjan算法的示例：

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 100 // 图的最大节点数

int index = 0; // 全局索引计数
int lowlink[MAX_NODES]; // 每个节点在遍历过程中的最低链接值
int visited[MAX_NODES]; // 每个节点是否已被访问
int stack[MAX_NODES]; // 记录遍历过程中访问的节点
int onStack[MAX_NODES]; // 每个节点是否在栈中
int stackIndex = 0; // 栈索引计数

int min(int a, int b) {
    return a < b ? a : b;
}

void Tarjan(int node, int graph[MAX_NODES][MAX_NODES]) {
    visited[node] = 1; // 标记节点已访问
    lowlink[node] = index;
    index++;
    stack[stackIndex] = node;
    onStack[node] = 1; // 将节点入栈
    stackIndex++;

    for (int i = 0; i < MAX_NODES; i++) {
        if (graph[node][i] == 1) { // 有连边到另一节点
            if (!visited[i]) { // 未访问过的节点
                Tarjan(i, graph); // 递归遍历
                lowlink[node] = min(lowlink[node], lowlink[i]);
            }
            else if (onStack[i]) { // 已在栈中的节点
                lowlink[node] = min(lowlink[node], lowlink[i]);
            }
        }
    }

    if (lowlink[node] == index - 1) { // 当前节点是强连通分量的根节点
        printf("Strongly Connected Component: ");
        int w;
        do {
            w = stack[--stackIndex];
            printf("%d ", w);
            onStack[w] = 0; // 将节点出栈
        } while (w != node);
        printf("\n");
    }
}

int main() {
    int graph[MAX_NODES][MAX_NODES] = {
        {0, 1, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {1, 0, 0, 1, 1},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 1, 0}
    };

    for (int i = 0; i < MAX_NODES; i++) {
        visited[i] = 0;
        onStack[i] = 0;
    }

    for (int i = 0; i < MAX_NODES; i++) {
        if (!visited[i]) {
            Tarjan(i, graph);
        }
    }

    return 0;
}

此示例中，我们定义了一个`Tarjan`函数来进行强连通分量的查找。我们通过输入一个图的邻接矩阵来调用此函数。在`Tarjan`函数中，我们使用一个全局索引计数来记录每个节点在遍历过程中的访问次序，使用`lowlink`数组来记录每个节点在遍历过程中的最低链接值。我们还使用了一个栈来辅助实现遍历过程。在函数中，我们首先标记节点为已访问，并且将其加入栈中，然后遍历与其相邻的节点，继续递归地遍历未访问过的节点。对于已访问的节点，我们通过更新`lowlink`数组来找到其最低链接值。当某个节点的`lowlink`值等于其在遍历过程中的索引值时，该节点以及所有其之前入栈的节点构成一个强连通分量。我们将这些节点出栈，输出强连通分量的内容。最后，在`main`函数中，我们创建一个示例图的邻接矩阵，并调用`Tarjan`函数来查找强连通分量。

请注意，这只是一个简单的示例，并且仅适用于使用邻接矩阵表示的有向图。实际应用中，可能需要根据具体情况进行修改。