Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.InputStreamReader;
- import java.io.PrintStream;
- import java.io.StreamTokenizer;
- import java.util.ArrayList;
- public class Main {
- int n;
- ArrayList<ArrayList<Integer> > g = new ArrayList<ArrayList<Integer> > (), gInv = new ArrayList<ArrayList<Integer> > ();
- StreamTokenizer in = new StreamTokenizer(new InputStreamReader(System.in));
- PrintStream out = new PrintStream(System.out);
- ArrayList<Integer> topSort = new ArrayList<Integer> ();
- boolean[] used;
- int[] component;
- void init() {
- ArrayList<Integer> tmp = new ArrayList<Integer> ();
- for(int i = 0; i < n; i++) {
- g.add(tmp);
- gInv.add(tmp);
- }
- used = new boolean[n];
- component = new int[n];
- }
- Main()throws Exception{
- int m, x, y;
- in.nextToken();
- n = (int)in.nval;
- in.nextToken();
- m = in.nextToken();
- init();
- for(int i = 0; i< m; i++) {
- in.nextToken();
- x = (int)in.nval;
- in.nextToken();
- y = (int)in.nval;
- g.get(x).add(y);
- gInv.get(y).add(x);
- }
- for(int i = 0; i < n; i++) {
- if(!used[i]) {
- top(i);
- }
- }
- }
- void top(int v) {
- used[v] = true;
- for(int i = 0; i < g.get(v).size(); i++) {
- if(!used[g.get(v).get(i)]) {
- top(g.get(v).get(i));
- }
- }
- topSort.add(v);
- }
- public static void main(String[] args) throws Exception {
- //Scanner in = new Scanner(System.in);
- new Main();
- }
- }
Add Comment
Please, Sign In to add comment