Pagini recente » Cod sursa (job #201754) | Cod sursa (job #2548740) | Cod sursa (job #1599769) | Cod sursa (job #2227447) | Cod sursa (job #2008661)
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;
if (graph[k] != null)
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;
if (tgraph[k] != null)
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();
}
}