Advertisement
Guest User

Untitled

a guest
Apr 20th, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.75 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3. import java.util.Stack;
  4.  
  5. import static java.util.Arrays.fill;
  6.  
  7. public class GraphBase {
  8.  
  9.     private static int time = 1;
  10.     private static int count = 1;
  11.  
  12.     private static class Graph {
  13.         public int comp, low, t;
  14.         ArrayList<Graph> edge = new ArrayList<Graph>();
  15.     }
  16.  
  17.     private static class Condensation {
  18.         public int min;
  19.         ArrayList<Graph> edge = new ArrayList<>();
  20.     }
  21.  
  22.     private static void Tarjan(Graph[] graph) {
  23.         for (Graph v: graph) {
  24.             v.t = 0;
  25.             v.comp = 0;
  26.         }
  27.         Stack<Graph> s = new Stack<>();
  28.         for (Graph v: graph){
  29.             if (v.t == 0){
  30.                 VisitVertex_Tarjan(graph, v, s);
  31.             }
  32.         }
  33.     }
  34.  
  35.     private static void VisitVertex_Tarjan(Graph[] graph, Graph v, Stack<Graph> s) {
  36.         v.t = time;
  37.         v.low = v.t;
  38.         time++;
  39.         s.push(v);
  40.         for(Graph u : v.edge) {
  41.             if(u.t == 0)
  42.                 VisitVertex_Tarjan(graph, u, s);
  43.             if(u.comp == 0 && v.low > u.low)
  44.                 v.low = u.low;
  45.         }
  46.         if(v.t == v.low) {
  47.             Graph u;
  48.             do {
  49.                 u = s.pop();
  50.                 u.comp = count;
  51.             } while(!(v.equals(u)));
  52.             count++;
  53.         }
  54.     }
  55.  
  56.  
  57.     public static void main (String[] args){
  58.         Scanner in = new Scanner(System.in);
  59.         int N = in.nextInt();
  60.         int M = in.nextInt();
  61.         Graph[] graph = new Graph[N];
  62.         for(int i = 0; i < N; i++){
  63.             graph[i] = new Graph();
  64.         }
  65.         for(int i = 0; i < M; i++){
  66.             int u = in.nextInt();
  67.             int v = in.nextInt();
  68.             graph[u].edge.add(graph[v]);
  69.         }
  70.         Tarjan(graph);
  71.         Condensation[] components = new Condensation[count];
  72.         for (int i = 0; i < count; i++){
  73.             components[i] = new Condensation();
  74.         }
  75.         for (Graph v : graph) {
  76.             int i = 0;
  77.             if(components[v.comp].edge.size() == 0)
  78.                 components[v.comp].min = i++;
  79.             components[v.comp].edge.add(v);
  80.         }
  81.         for(int v = 0; v < N; v++) {
  82.             if(components[graph[v].comp].edge.size() == 0)
  83.                 components[graph[v].comp].min = v;
  84.             components[graph[v].comp].edge.add(graph[v]);
  85.         }
  86.         boolean[] base = new boolean[count];
  87.         fill(base, false);
  88.         for(Graph v : graph) {
  89.             for(Graph u : v.edge) {
  90.                 if(v.comp != u.comp)
  91.                     base[u.comp] = true;
  92.             }
  93.         }
  94.         for(int i = 1; i < count; i++)
  95.             if (!base[i])
  96.         System.out.print(components[i].min + " ");
  97.     }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement