Pagini recente » Cod sursa (job #3241480) | Cod sursa (job #1741300) | Cod sursa (job #1316929) | Cod sursa (job #1929083) | Cod sursa (job #2679585)
package com.company;
import java.util.*;
import java.io.*;
public class Dfs {
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);
}
}
}