그래프에서 강하게 연결된 구성 요소
13220 단어 javagraphalgorithms
'V' 꼭지점과 'E' 가장자리의 비가중 방향성 그래프가 제공됩니다. 귀하의 작업은 그래프에 있는 SCC(strongly connected component)를 인쇄하는 것입니다.
입력 형식:
아니오인 'n'이 주어집니다. 그래프의 꼭짓점 수(0 기준 인덱스)
'edges' 크기 m*2의 2d 배열, 여기서 m은 아니오입니다. 모서리의 2는 모서리가 존재하는 두 정점입니다. 즉
edges[i][0]---->edges[i][1]
노드 0
와 1
사이에 에지가 있습니다.TC: topo sort = O(N+E) +
transpose of the graph = O(N+E) +
dfs on topo sort with transpose graph = O(N+E)
import java.util.*;
public class Solution {
public static List<List<Integer>> stronglyConnectedComponents(int n, int[][] edges) {
List<List<Integer>> list = new ArrayList<>();
// Write your code here
// we identify which are the strogly conected component,
// strongly connected components are the components where all the
//are reachable by every other node in the component.
//steps to solve this using kosaraju's SCC
//1. find toposort of the graph.
//2. transpose the graph(change direction of the edges)
//3. do dfs on the toposort with the transpose graph.
//creating adjacency list
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
ArrayList<ArrayList<Integer>> tadj = new ArrayList<>();
for(int i =0;i<n;i++) {
adj.add(new ArrayList<>());
tadj.add(new ArrayList<>());
}
for(int ed [] : edges) {
//creating adjacency graph
ArrayList<Integer> temp = adj.get(ed[0]);
temp.add(ed[1]);
adj.set(ed[0],temp);
//creating transpose adjacency graph
ArrayList<Integer> temp2 = tadj.get(ed[1]);
temp2.add(ed[0]);
tadj.set(ed[1],temp2);
}
int visited[] = new int[n];
Stack<Integer> stack = new Stack<>();
for(int i =0;i<n;i++){
if(visited[i]==0){
dfs(i,visited,stack,adj);
}
}
//now stack has topo sorted nodes in it.
Arrays.fill(visited,0);
while(!stack.isEmpty()){
int node = stack.pop();
if(visited[node] ==0){
ArrayList<Integer> connComp = new ArrayList<>();
dfsOnTransposeGraph(node,visited,tadj,connComp);
list.add(connComp);
}
}
return list;
}
public static void dfsOnTransposeGraph(int node, int[] visited,
ArrayList<ArrayList<Integer>> adj,ArrayList<Integer> connComp){
visited[node] = 1;
connComp.add(node);
for(Integer it : adj.get(node)){
if(visited[it]==0) {
dfsOnTransposeGraph(it,visited,adj,connComp);
}
}
}
public static void dfs(int node, int[] visited, Stack<Integer> stack,
ArrayList<ArrayList<Integer>> adj){
visited[node] = 1;
for(Integer it : adj.get(node)){
if(visited[it]==0) dfs(it,visited,stack,adj);
}
stack.push(node);
}
}
Reference
이 문제에 관하여(그래프에서 강하게 연결된 구성 요소), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/prashantrmishra/strongly-connected-components-in-the-graph-1bih텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)