Articulation Points (or Cut Vertices) in a Graph shows different result for different order of edges

Question

Definition: An articulation point is a node whose removal increases the number of connected components in the graph.

import java.util.ArrayList;

public class ArticulationPoints {
static int TIME;

static void APUtil(ArrayList<ArrayList<Integer>> adj, int u,
                   boolean visited[], int disc[], int low[],
                   int parent, boolean isAP[]) {
    int children = 0;
    visited[u] = true;
    disc[u] = low[u] = TIME++;

    for (Integer v : adj.get(u)) {
        if (!visited[v]) {
            children++;
            APUtil(adj, v, visited, disc, low, u, isAP);
            low[u] = Math.min(low[u], low[v]);

            if (parent == -1 && children > 1)
                isAP[u] = true;
            if (parent != -1 && low[v] >= disc[u])
                isAP[u] = true;
        } else if (v != parent) {
            low[u] = Math.min(low[u], disc[v]);
        }
    }
}

static void AP(ArrayList<ArrayList<Integer>> adj, int V) {
    boolean[] visited = new boolean[V];
    int[] disc = new int[V];
    int[] low = new int[V];
    boolean[] isAP = new boolean[V];
    TIME = 0;
    int par = -1;

    for (int u = 0; u < V; u++) {
        if (!visited[u]) {
            APUtil(adj, u, visited, disc, low, par, isAP);
        }
    }

    System.out.println("Articulation Points in the Graph:");
    for (int u = 0; u < V; u++) {
        if (isAP[u]) {
            System.out.print(u + " ");
        }
    }
    System.out.println();
}

public static void main(String[] args) {
    // Graph 1
    int V1 = 7;
    ArrayList<ArrayList<Integer>> adj1 = new ArrayList<>();
    for (int i = 0; i < V1; i++) {
        adj1.add(new ArrayList<>());
    }
    adj1.get(0).add(2);
    adj1.get(2).add(1);
    adj1.get(1).add(0);
    adj1.get(0).add(4);
    adj1.get(2).add(3);
    adj1.get(4).add(5);
    adj1.get(5).add(6);
    adj1.get(6).add(3);

    System.out.println("Graph 1:");
    AP(adj1, V1);

    // Graph 2
    int V2 = 7;
    ArrayList<ArrayList<Integer>> adj2 = new ArrayList<>();
    for (int i = 0; i < V2; i++) {
        adj2.add(new ArrayList<>());
    }
    adj2.get(0).add(4);
    adj2.get(0).add(2);
    adj2.get(2).add(1);
    adj2.get(1).add(0);
    adj2.get(2).add(3);
    adj2.get(4).add(5);
    adj2.get(5).add(6);
    adj2.get(6).add(3);

    System.out.println("Graph 2:");
    AP(adj2, V2);
}

}

I am trying to understand why different order of edges is giving different result? I am trying with gfg code to find articulation point. I was checking the effect of Cross edge in this case and for this graph I am not able to get correct answer.

Output
Graph 1:
Articulation Points in the Graph:
0 2 
Graph 2:
Articulation Points in the Graph:
0 4 5 6 ```

Answer 1

The Tarjan algorithm works only for undirected graphs.

"The classic sequential algorithm for computing biconnected components in a connected undirected graph is due to John Hopcroft and Robert Tarjan" https://en.wikipedia.org/wiki/Biconnected_component

" A C++ program to find biconnected components in a given undirected graph" https://www.geeksforgeeks.org/biconnected-components/

You are getting inconsistent results for the same, but differently specified, graph because you are mis-applying the algorithm.

Note that if your graph is undirected, then there no articulation points ( you can remove any vertex and the graph remains biconnected )

FYI, here are the C++ unit tests for your graph and the PathFinder graph theory library implementation of the Tarjan algrithm https://github.com/JamesBremner/PathFinder

TEST(AP_so76642739_undirected)
{
    raven::graph::sGraphData gd;
    gd.g.add("0", "2");
    gd.g.add("2", "1");
    gd.g.add("1", "0");
    gd.g.add("0", "4");
    gd.g.add("2", "3");
    gd.g.add("4", "5");
    gd.g.add("5", "6");
    gd.g.add("6", "3");
    raven::graph::cTarjan T;
    auto vAP = T.ArticulationPoints(gd);
    CHECK_EQUAL(0, vAP.size());
}

TEST(AP_so76642739_undirected_2)
{
    // define edges in a different order
    raven::graph::sGraphData gd;
    gd.g.add("0", "4");
    gd.g.add("0", "2");
    gd.g.add("2", "1");
    gd.g.add("1", "0");
    gd.g.add("2", "3");
    gd.g.add("4", "5");
    gd.g.add("5", "6");
    gd.g.add("6", "3");
    raven::graph::cTarjan T;
    auto vAP = T.ArticulationPoints(gd);
    CHECK_EQUAL(0, vAP.size());
}

TEST(AP_so76642739_directed)
{
    raven::graph::sGraphData gd;
    gd.g.directed();
    gd.g.add("0", "2");
    gd.g.add("2", "1");
    gd.g.add("1", "0");
    gd.g.add("0", "4");
    gd.g.add("2", "3");
    gd.g.add("4", "5");
    gd.g.add("5", "6");
    gd.g.add("6", "3");
    raven::graph::cTarjan T;
    try
    {
        auto vAP = T.ArticulationPoints(gd);
        CHECK(false);
    }
    catch( ... )
    {}
}