Cod sursa(job #2008657)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 7 august 2017 11:09:19
Problema Componente tare conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.78 kb
import java.io.*;
import java.util.*;

public class Main {
	static int nr = 0;
	static int n;
	static ArrayList[] graph;
	static ArrayList[] tgraph;
	static ArrayList[] result;
	static int[] v, vect;
	static void DFS(int k, ArrayList[] graph){
		v[k] = 1;
		int q, i = 0;;
		while ( i < graph[k].size()){
			q = (int) graph[k].get(i);
			if (v[q] == 0)
				DFS(q, graph);
			i++;
		}
		nr++;
		vect[nr] = k;
	}
	
	static void DFS2(int k, int nr, int s){
		if (s == 1)
			result[nr].add(k);
		v[k] = 1;
		int q, i = 0;
		while ( i < tgraph[k].size()){
			q = (int) tgraph[k].get(i);
			if (v[q] == 0)
				DFS2(q, nr, s);
			i++;
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader scanner = null;
		PrintWriter printer = null;
		int 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]);
		v = new int[n+1];
		vect = new int[n+1];
		for (i = 1; i <= n; i++)
			v[i] = 0;
		
		graph = new ArrayList[n+1];
		tgraph = new ArrayList[n+1];
		
		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]);
			if (graph[a] == null)
				graph[a] = new ArrayList<Integer>();
			if (tgraph[b] == null)
				tgraph[b] = new ArrayList<Integer>();
			graph[a].add(b);
			tgraph[b].add(a);
		}
		
		for (i = 1; i <= n; i++)
			if (v[i] == 0)
				DFS(i, graph);
		
		for (i = 1; i <= n; i++)
			v[i] = 0;
		nr = 0;
		int nrc = 0;
		for (i = n; i >= 1; i--)
			if (v[vect[i]] == 0){
				nrc++;
				DFS2(vect[i], nrc, 0);
			}
		result = new ArrayList[nrc+1];
		for (i = 1; i <= nrc; i++)
			result[i] = new ArrayList<Integer>();
		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], nr, 1);
			}
		
		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();
	}
}