Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Scanner;
- import java.util.Stack;
- import static java.util.Arrays.fill;
- public class GraphBase {
- private static int time = 1;
- private static int count = 1;
- private static class Graph {
- public int comp, low, t;
- ArrayList<Graph> edge = new ArrayList<Graph>();
- }
- private static class Condensation {
- public int min;
- ArrayList<Graph> edge = new ArrayList<>();
- }
- private static void Tarjan(Graph[] graph) {
- for (Graph v: graph) {
- v.t = 0;
- v.comp = 0;
- }
- Stack<Graph> s = new Stack<>();
- for (Graph v: graph){
- if (v.t == 0){
- VisitVertex_Tarjan(graph, v, s);
- }
- }
- }
- private static void VisitVertex_Tarjan(Graph[] graph, Graph v, Stack<Graph> s) {
- v.t = time;
- v.low = v.t;
- time++;
- s.push(v);
- for(Graph u : v.edge) {
- if(u.t == 0)
- VisitVertex_Tarjan(graph, u, s);
- if(u.comp == 0 && v.low > u.low)
- v.low = u.low;
- }
- if(v.t == v.low) {
- Graph u;
- do {
- u = s.pop();
- u.comp = count;
- } while(!(v.equals(u)));
- count++;
- }
- }
- public static void main (String[] args){
- Scanner in = new Scanner(System.in);
- int N = in.nextInt();
- int M = in.nextInt();
- Graph[] graph = new Graph[N];
- for(int i = 0; i < N; i++){
- graph[i] = new Graph();
- }
- for(int i = 0; i < M; i++){
- int u = in.nextInt();
- int v = in.nextInt();
- graph[u].edge.add(graph[v]);
- }
- Tarjan(graph);
- Condensation[] components = new Condensation[count];
- for (int i = 0; i < count; i++){
- components[i] = new Condensation();
- }
- for (Graph v : graph) {
- int i = 0;
- if(components[v.comp].edge.size() == 0)
- components[v.comp].min = i++;
- components[v.comp].edge.add(v);
- }
- for(int v = 0; v < N; v++) {
- if(components[graph[v].comp].edge.size() == 0)
- components[graph[v].comp].min = v;
- components[graph[v].comp].edge.add(graph[v]);
- }
- boolean[] base = new boolean[count];
- fill(base, false);
- for(Graph v : graph) {
- for(Graph u : v.edge) {
- if(v.comp != u.comp)
- base[u.comp] = true;
- }
- }
- for(int i = 1; i < count; i++)
- if (!base[i])
- System.out.print(components[i].min + " ");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement