Pagini recente » Cod sursa (job #288248) | Cod sursa (job #889399) | Cod sursa (job #1600094) | Cod sursa (job #2096433) | Cod sursa (job #2679587)
import java.util.*;
import java.io.*;
public class Main {
private static int n;
private static int m;
private static ArrayList<Integer> [] graph;
private static boolean [] visited;
private static int count;
public static void main(String []args) {
File inputFile = new File("dfs.in");
File outputFile = new File("dfs.out");
try {
FileInputStream inputStream = new FileInputStream(inputFile);
Scanner scanner = new Scanner(inputStream);
n = scanner.nextInt(); // number of nodes - how many lists
m = scanner.nextInt(); // number of edges - how many rows
graph = new ArrayList[n];
visited = new boolean [n];
for (int i = 0; i < n; i++){
graph[i] = new ArrayList<Integer>();
}
for (int i = 0; i < m; i++){
int x = scanner.nextInt();
int y = scanner.nextInt();
graph[x - 1].add(y - 1);
graph[y - 1].add(x - 1);
}
inputStream.close();
for (int i = 0; i < n; i++){
if (!visited[i]){
traverse(i);
count++;
}
}
FileOutputStream outputStream = new FileOutputStream(outputFile);
PrintWriter writer = new PrintWriter(outputStream);
writer.println(count);
writer.close();
outputStream.close();
} catch(IOException e) {
}
}
private static void traverse(int i) {
visited[i] = true;
for (int adjacentNode: graph[i]) {
if (!visited[adjacentNode])
traverse(adjacentNode);
}
}
}