Pagini recente » Cod sursa (job #867017) | Cod sursa (job #747260) | Cod sursa (job #571976) | Cod sursa (job #2581762) | Cod sursa (job #1705783)
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.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class Main {
static int numEdges;
static int numNodes;
static int source;
static boolean[] isVisited;
public static void dfs(ArrayList<ArrayList<Integer>> edge,int source){
Stack<Integer> s = new Stack<Integer>();
s.push(source);
isVisited[source] = true;
while(!s.isEmpty()){
int n = s.peek();
ArrayList<Integer> neighbour = edge.get(n);
for (Integer e : neighbour){
if (!isVisited[e]){
isVisited[e] = true;
s.add(e);
//System.out.println(e.end);
//System.out.println(result);
}
}
s.pop();
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BufferedReader in = null;
ArrayList<ArrayList<Integer>> edges = new ArrayList<ArrayList<Integer>>(); //lista muchiilor pe care trebuie sa o pastram nesortata pt a putea face rost de muchiile alternative
int result=0;
try {
in = new BufferedReader(new FileReader("dfs.in"));
String[] aux = in.readLine().split(" ");
numNodes = Integer.parseInt(aux[0]);
numEdges = Integer.parseInt(aux[1]);
isVisited = new boolean[numNodes];
for (int i=0;i<numNodes;i++)
isVisited[i] = false;
for (int i=0;i<numNodes;i++)
edges.add(new ArrayList<Integer>());
for (int i = 0 ; i < numEdges ; i++){
aux = in.readLine().split(" ");
int s = Integer.parseInt(aux[0])-1;
int e = Integer.parseInt(aux[1])-1;
edges.get(s).add(e);
}
for (int i=0;i<numNodes;i++){
if (!isVisited[i]){
dfs(edges,i);
result+=1;
}
}
} catch (IOException e) {
e.printStackTrace();
} finally {
if (in != null) {
try {
in.close();
} catch (IOException e) {
}
}
}
try {
BufferedWriter bufferedOut = new BufferedWriter( new FileWriter("dfs.out"));
PrintWriter out = new PrintWriter(bufferedOut);
out.print(result);
System.out.println(result);
out.close();
bufferedOut.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}