Pagini recente » Cod sursa (job #586117) | Cod sursa (job #1663021) | Rezultatele filtrării | Cod sursa (job #3236725) | Cod sursa (job #1705803)
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.pop();
ArrayList<Integer> neighbour = edge.get(n);
for (Integer e : neighbour){
if (!isVisited[e]){
isVisited[e] = true;
s.push(e);
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BufferedReader in = null;
ArrayList<ArrayList<Integer>> edges = new ArrayList<ArrayList<Integer>>();
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);
edges.get(e).add(s);
}
for (int i=0;i<numNodes;i++){
if (!isVisited[i]){
result++;
dfs(edges,i);
}
}
} 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();
}
}
}