Pagini recente » Cod sursa (job #3173172) | Cod sursa (job #679670) | Cod sursa (job #2262175) | Cod sursa (job #440547) | Cod sursa (job #2191812)
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(new FileReader("dfs.in"));
UndirectedGraph graph = new UndirectedGraph(scanner.nextInt());
int numEdges = scanner.nextInt();
for (int i=0; i<numEdges; i++) {
graph.addEdge(scanner.nextInt(), scanner.nextInt());
}
scanner.close();
Writer writer = new PrintWriter("dfs.out");
writer.write(graph.getConnectedComponents());
writer.close();
}
}
class UndirectedGraph {
private List<List<Integer>> adjList;
private List<Boolean> visitedVertices;
public UndirectedGraph(int numVertices) {
if (numVertices < 1) {
throw new IllegalArgumentException("number of vertices should be a positive number");
}
adjList = new ArrayList<>(numVertices);
}
public void addEdge(int source, int destination) {
if (source < 0 || source >= adjList.size()) {
throw new IllegalArgumentException("invalid source provided");
}
if (destination < 0 || destination >= adjList.size()) {
throw new IllegalArgumentException("invalid destination provided");
}
if (adjList.get(source) == null) {
adjList.set(source, new LinkedList<>());
}
if (adjList.get(destination) == null) {
adjList.set(destination, new LinkedList<>());
}
adjList.get(source).add(destination);
adjList.get(destination).add(source);
}
public int getConnectedComponents() {
visitedVertices = new ArrayList<>(adjList.size());
int connectedComponents = 0;
for (Integer vertix=0; vertix<adjList.size(); vertix++) {
if (!visitedVertices.get(vertix)) {
dfs(vertix);
connectedComponents++;
}
}
return connectedComponents;
}
private void dfs(Integer vertex) {
visitedVertices.set(vertex, true);
for (Integer adjVertix : adjList.get(vertex)) {
if (!visitedVertices.get(adjVertix)) {
dfs(adjVertix);
}
}
}
}