Pagini recente » Cod sursa (job #930004) | Cod sursa (job #770154) | Cod sursa (job #1556361) | Cod sursa (job #183182) | Cod sursa (job #2191827)
import java.io.*;
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 BufferedInputStream(new FileInputStream("dfs.in")));
UndirectedGraph graph = new UndirectedGraph(scanner.nextInt());
int numEdges = scanner.nextInt();
for (int i=0; i<numEdges; i++) {
graph.addEdge(scanner.nextInt()-1, scanner.nextInt()-1);
}
scanner.close();
PrintWriter printWriter = new PrintWriter("dfs.out");
printWriter.print(graph.getConnectedComponents());
printWriter.close();
}
}
class UndirectedGraph {
private List<Integer>[] adjList;
private boolean[] visitedVertices;
public UndirectedGraph(int numVertices) {
if (numVertices < 1) {
throw new IllegalArgumentException("number of vertices should be a positive number");
}
adjList = new List[numVertices];
}
public void addEdge(int source, int destination) {
if (source < 0 || source >= adjList.length) {
throw new IllegalArgumentException("invalid source provided");
}
if (destination < 0 || destination >= adjList.length) {
throw new IllegalArgumentException("invalid destination provided");
}
if (adjList[source] == null) {
adjList[source] = new LinkedList<>();
}
if (adjList[destination] == null) {
adjList[destination] = new LinkedList<>();
}
adjList[source].add(destination);
adjList[destination].add(source);
}
public int getConnectedComponents() {
visitedVertices = new boolean[adjList.length];
int connectedComponents = 0;
for (int vertix=0; vertix<adjList.length; vertix++) {
if (!visitedVertices[vertix]) {
dfs(vertix);
connectedComponents++;
}
}
return connectedComponents;
}
private void dfs(int vertex) {
visitedVertices[vertex] = true;
List<Integer> adjVertices = adjList[vertex];
if (adjVertices != null) {
for (int adjVertix : adjVertices) {
if (!visitedVertices[adjVertix]) {
dfs(adjVertix);
}
}
}
}
}