Pagini recente » Istoria paginii runda/simulare-cartita-33 | Cod sursa (job #2493584) | Cod sursa (job #732469) | preoji/clasament/9 | Cod sursa (job #3122829)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
static class Task {
public static final String INPUT_FILE = "in";
public static final String OUTPUT_FILE = "out";
// numarul maxim de noduri
public static final int NMAX = (int)1e5 + 5; // 10^5 + 5 = 100.005
// n = numar de noduri, m = numar de muchii/arce
int n, m;
// adj[node] = lista de adiacenta a nodului node
// exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
@SuppressWarnings("unchecked")
ArrayList<Integer> adj[] = new ArrayList[NMAX];
public void solve() {
readInput();
writeOutput(getResult());
}
private void readInput() {
try {
Scanner sc = new Scanner(new BufferedReader(new FileReader(
INPUT_FILE)));
n = sc.nextInt();
m = sc.nextInt();
for (int node = 1; node <= n; node++) {
adj[node] = new ArrayList<>();
}
for (int i = 1, x, y; i <= m; i++) {
// arc (x, y)
x = sc.nextInt();
y = sc.nextInt();
adj[x].add(y);
}
sc.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private void writeOutput(ArrayList<Integer> topsort) {
try {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
OUTPUT_FILE)));
for (Integer node : topsort) {
pw.printf("%d ", node);
}
pw.printf("\n");
pw.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private void dfs(int node, ArrayList<Integer> topSort, int[] visited) {
visited[node] = 1;
for (Integer neigh : adj[node]) {
if (visited[neigh] == 0) {
dfs(neigh, topSort, visited);
}
}
}
private ArrayList<Integer> getResult() {
int[] visited = new int[n + 1];
for (int i = 0; i <= n; i++) {
visited[i] = 0;
}
Integer result = 0;
for (int node = 1; node <= n; node++) {
if (visited[node] == 0) {
dfs(node, result, visited);
result = result + 1;
}
}
Collections.reverse(topsort);
return topsort;
}
}
public static void main(String[] args) {
new Task().solve();
}
}