Mike Tarzan

gistfile1.txt

// https://binarysearch.com/problems/Edges-that-Disconnect-the-Graph
import java.util.*;

class Solution {

    static class Result {
        int lowLink;
        boolean isCycle;

        Result(int lowLink, boolean isCycle) {
            this.lowLink = lowLink;
            this.isCycle = isCycle;
        }
    }

    public int solve(int[][] graph) {
        lowLink = new int[graph.length];
        for(int i = 0; i < graph.length; i++) {
            lowLink[i] = i;
        }
        dfs(graph, 0, new HashSet<>());
        
        System.out.println(Arrays.toString(lowLink));

        Set<Integer> scc = new HashSet<>();
        for(int l : lowLink) scc.add(l);

        return scc.size() - 1;
    }

    Set<String> usedEdge = new HashSet<>();
    int[] lowLink;

    Result dfs(int[][] graph, int index, Set<Integer> stack) {
        if(stack.contains(index)) {
            return new Result(lowLink[index], true);
        }
        stack.add(index);

        boolean hasCycle = false;
        
        for(int neigh : graph[index]) {
            String edge = edgeIdentifier(index, neigh);
            if(!usedEdge.contains(edge)) {
                usedEdge.add(edge);
                Result r = dfs(graph, neigh, stack);
                hasCycle = hasCycle || r.isCycle;
                if(r.isCycle) {
                    lowLink[index] = Math.min(lowLink[index], r.lowLink);
                }
            }
        }
        stack.remove(index);

        if(lowLink[index] == index) {
            return new Result(lowLink[index], false);
        }

        return new Result(lowLink[index], hasCycle);
    }

    String edgeIdentifier(int a, int b) {
        int m = Math.min(a, b);
        int n = Math.max(a, b);
        return m + "," + n;
    }

}