Cod sursa(job #2191827)

Utilizator ibicecIT Zilla ibicec Data 3 aprilie 2018 20:09:03
Problema Parcurgere DFS - componente conexe Scor 55
Compilator java Status done
Runda Arhiva educationala Marime 2.35 kb
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);
                }
            }
        }
    }

}