Pagini recente » Cod sursa (job #2290737) | Cod sursa (job #1048992) | Cod sursa (job #642703) | Cod sursa (job #1560374) | Cod sursa (job #1359305)
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.Map;
import java.util.StringTokenizer;
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());
}
}
class Vertex {
public int value;
public LinkedList<Integer> inEdges;
public LinkedList<Integer> outEdges;
public Vertex(int vertexValue) {
value = vertexValue;
inEdges = new LinkedList<Integer>();
outEdges = new LinkedList<Integer>();
}
}
public class Main {
private static HashMap<Integer, Vertex> graph;
private static void readGraph() {
InputReader ir = new InputReader("sortaret.in", " ");
int vertexCount = ir.nextInt();
int edgeCount = ir.nextInt();
for (; edgeCount > 0; edgeCount--) {
int nodeOut = ir.nextInt();
int nodeIn = ir.nextInt();
if (!graph.containsKey(nodeIn)) {
Vertex newVertex = new Vertex(nodeIn);
newVertex.inEdges.add(nodeOut);
graph.put(nodeIn, newVertex);
} else {
graph.get(nodeIn).inEdges.add(nodeOut);
}
if (!graph.containsKey(nodeOut)) {
Vertex newVertex = new Vertex(nodeOut);
newVertex.outEdges.add(nodeIn);
graph.put(nodeOut, newVertex);
} else {
graph.get(nodeOut).outEdges.add(nodeIn);
}
}
ir.closeReader();
}
public static LinkedList<Integer> sortp() {
LinkedList<Integer> sortedList = new LinkedList<Integer>();
LinkedList<Vertex> initialList = new LinkedList<Vertex>();
Iterator it = graph.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Integer, Vertex> entry = (Map.Entry<Integer, Vertex>) it.next();
Vertex currentVertex = entry.getValue();
if (currentVertex.inEdges.size() == 0) {
initialList.add(currentVertex);
}
}
while (initialList.size() > 0) {
Iterator listit = initialList.iterator();
Vertex popVertex = (Vertex) listit.next();
listit.remove();
sortedList.add(popVertex.value);
for (int vertexIndex : popVertex.outEdges) {
Vertex outVertex = graph.get(vertexIndex);
if (outVertex.inEdges.size() == 1) {
initialList.add(outVertex);
}
}
}
return sortedList;
}
private static void writeOutput(LinkedList<Integer> topsort) {
try {
PrintWriter pr = new PrintWriter("sortaret.out");
for (int vertex : topsort) {
pr.write(vertex + " ");
}
pr.close();
} catch (FileNotFoundException ex) {
ex.printStackTrace();
}
}
public static void main(String[] args) {
graph = new HashMap<Integer, Vertex>();
readGraph();
writeOutput(sortp());
}
}