Pagini recente » Cod sursa (job #662964) | Istoria paginii utilizator/robertanechita | Statistici Cristian Bota Avram (CristiBota3) | Monitorul de evaluare | Cod sursa (job #2008652)
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){
v[k] = 1;
int q, i = 0;;
while ( i < graph[k].size()){
q = (int) graph[k].get(i);
if (v[q] == 0)
DFS(q);
i++;
}
nr++;
vect[nr] = k;
}
static void DFS2(int k, int nr){
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);
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];
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);
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);
}
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();
}
}