Cod sursa(job #2008646)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 7 august 2017 09:43:05
Problema Componente tare conexe Scor 90
Compilator java Status done
Runda Arhiva educationala Marime 2.55 kb
import java.io.*;
import java.util.*;

public class Main {
	static int nr = 0;
	static void DFS(int k, int v[], ArrayList[] graph, int vect[]){
		v[k] = 1;
		int q, i = 0;;
		while ( i < graph[k].size()){
			q = (int) graph[k].get(i);
			if (v[q] == 0)
				DFS(q, v, graph, vect);
			i++;
		}
		nr++;
		vect[nr] = k;
	}
	
	static void DFS2(int k, int v[], ArrayList[] graph, ArrayList list){
		list.add(k);
		v[k] = 1;
		int q, i = 0;
		while ( i < graph[k].size()){
			q = (int) graph[k].get(i);
			if (v[q] == 0)
				DFS2(q, v, graph, list);
			i++;
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader scanner = null;
		PrintWriter printer = null;
		int n, m, a, b, i, j;

		try{
			FileReader file = new FileReader("ctc.in");
			scanner = new BufferedReader(file);
			printer = new PrintWriter("ctc.out");
		} catch (FileNotFoundException e)
		{
			System.out.println("File not found!\n");
		}
		
		String input = "";
		String[] numbers;
		try {
			input = scanner.readLine();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		numbers = input.split(" ");
		n = Integer.parseInt(numbers[0]);
		m = Integer.parseInt(numbers[1]);
		int[] v = new int[n+1];
		int[] vect = new int[n+1];
		for (i = 1; i <= n; i++)
			v[i] = 0;
		ArrayList[] graph = new ArrayList[n+1];
		ArrayList[] tgraph = new ArrayList[n+1];
		ArrayList[] result = new ArrayList[n+1];
		for (i = 1; i <= n; i++){
			graph[i] = new ArrayList<Integer>();
			tgraph[i] = new ArrayList<Integer>();
			result[i] = new ArrayList<Integer>();
		}
		for (i = 1; i <= m; i++)
		{
			try {
				input = scanner.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			numbers = input.split(" ");
			a = Integer.parseInt(numbers[0]);
			b = Integer.parseInt(numbers[1]);
			graph[a].add(b);
			tgraph[b].add(a);
		}
		
		for (i = 1; i <= n; i++)
			if (v[i] == 0)
				DFS(i, v, graph, vect);
		
		for (i = 1; i <= n; i++)
			v[i] = 0;
		nr = 0;
		
		for (i = n; i >= 1; i--)
			if (v[vect[i]] == 0){
				nr++;
				DFS2(vect[i], v, tgraph, result[nr]);
			}
		printer.println(nr);
		for (i = 1; i <= nr; i++)
		{
			for (j = 0; j < result[i].size(); j++){
				a = (int)result[i].get(j);
				printer.print(a+" ");
			}
			printer.println();
		}
		try {
			scanner.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		printer.close();
	}
}