Guest User

Untitled

a guest
Jan 23rd, 2018
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.66 KB | None | 0 0
  1. import java.io.InputStreamReader;
  2. import java.io.PrintStream;
  3. import java.io.StreamTokenizer;
  4. import java.util.ArrayList;
  5.  
  6. public class Main {  
  7.     int n;
  8.     ArrayList<ArrayList<Integer> > g = new ArrayList<ArrayList<Integer> > (), gInv = new ArrayList<ArrayList<Integer> > ();
  9.     StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
  10.     PrintStream out = new PrintStream(System.out);
  11.     ArrayList<Integer> topSort = new ArrayList<Integer> ();
  12.     boolean[] used;
  13.     int[] component;
  14.    
  15.     void init() {        
  16.         ArrayList<Integer> tmp = new ArrayList<Integer> ();
  17.         for(int i = 0; i < n; i++) {
  18.             g.add(tmp);
  19.             gInv.add(tmp);
  20.         }
  21.         used = new boolean[n];  
  22.         component = new int[n];
  23.     }
  24.    
  25.     Main()throws Exception{  
  26.         int m, x, y;
  27.        
  28.         in.nextToken();
  29.         n = (int)in.nval;
  30.         in.nextToken();
  31.         m = in.nextToken();
  32.        
  33.         init();
  34.        
  35.         for(int i = 0; i< m; i++) {
  36.             in.nextToken();
  37.             x = (int)in.nval;
  38.             in.nextToken();
  39.             y = (int)in.nval;
  40.             g.get(x).add(y);
  41.             gInv.get(y).add(x);
  42.         }
  43.          for(int i = 0; i < n; i++) {
  44.              if(!used[i]) {
  45.                  top(i);
  46.              }
  47.          }
  48.  
  49.     }
  50.    
  51.     void top(int v) {
  52.         used[v] = true;
  53.         for(int i = 0; i < g.get(v).size(); i++) {
  54.             if(!used[g.get(v).get(i)]) {
  55.                 top(g.get(v).get(i));
  56.             }
  57.         }
  58.         topSort.add(v);
  59.     }
  60.    
  61.     public static void main(String[] args) throws Exception {
  62.         //Scanner in = new Scanner(System.in);
  63.         new Main();
  64.     }
  65.  
  66.    
  67. }
Add Comment
Please, Sign In to add comment