Pagini recente » Cod sursa (job #1618140) | Cod sursa (job #1796606) | Cod sursa (job #2672960) | Cod sursa (job #823737) | Cod sursa (job #1369005)
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
class Vertex {
LinkedList<Integer> edges;
int vertex;
boolean visited;
public Vertex(int indexVertex) {
vertex = indexVertex;
edges = new LinkedList<Integer>();
visited = false;
}
public int getIndex() {
return this.vertex;
}
}
class InputReader {
private FileInputStream fs;
private BufferedReader br;
private StringTokenizer st;
private final String delim;
public InputReader(String fileName, String delim) {
this.delim = delim;
try {
fs = new FileInputStream(fileName);
br = new BufferedReader(new InputStreamReader(fs));
} catch (FileNotFoundException ex) {
ex.printStackTrace();
}
}
public void closeReader() {
try {
br.close();
fs.close();
} catch (IOException ex) {
ex.printStackTrace();
}
}
public String nextString() {
while (st == null || !st.hasMoreElements()) {
String line = null;
try {
line = br.readLine();
if (line != null && !line.isEmpty()) {
st = new StringTokenizer(line);
} else {
return null;
}
} catch (IOException ex) {
ex.printStackTrace();
}
return st.nextToken();
}
return st.nextToken(delim);
}
public byte nextByte() {
return Byte.parseByte(nextString());
}
public short nextShort() {
return Short.parseShort(nextString());
}
public int nextInt() {
return Integer.parseInt(nextString());
}
public long nextLong() {
return Long.parseLong(nextString());
}
}
public class Main {
private static HashMap<Integer, Vertex> graph;
private static LinkedList<Integer> topsort;
public static void addEdge(int outVertex, int inVertex) {
if (graph.containsKey(outVertex)) {
if (!graph.get(outVertex).edges.contains(inVertex)) {
graph.get(outVertex).edges.add(inVertex);
}
} else {
Vertex newVertex = new Vertex(outVertex);
newVertex.edges.add(inVertex);
graph.put(outVertex, newVertex);
}
if (!graph.containsKey(inVertex)) {
graph.put(inVertex, new Vertex(inVertex));
}
}
public static void DFS(Vertex currentNode) {
if (!topsort.contains(currentNode.vertex)) {
topsort.add(currentNode.vertex);
}
for (int ver : currentNode.edges) {
if (graph.containsKey(ver)) {
DFS(graph.get(ver));
}
}
}
private static void readGraph() {
InputReader ir = new InputReader("sortaret.in", " ");
int vertexCount = ir.nextInt();
int edgeCount = ir.nextInt();
for (int edgeIndex = 0; edgeIndex < edgeCount; edgeIndex++) {
addEdge(ir.nextInt(), ir.nextInt());
}
ir.closeReader();
}
private static void writeOutput(LinkedList<Integer> topsort) {
try {
PrintWriter pr = new PrintWriter("sortaret.out");
for (int vertex : topsort) {
pr.write(vertex + " ");
}
pr.println();
pr.close();
} catch (FileNotFoundException ex) {
ex.printStackTrace();
}
}
public static void main(String[] args) {
graph = new HashMap<Integer, Vertex>();
topsort = new LinkedList<Integer>();
readGraph();
for (Map.Entry<Integer, Vertex> entry : graph.entrySet()) {
if (!topsort.contains(entry.getValue().vertex)) {
DFS(entry.getValue());
}
}
writeOutput(topsort);
}
}