Cod sursa(job #2191812)

Utilizator ibicecIT Zilla ibicec Data 3 aprilie 2018 19:37:34
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.28 kb
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);
            }
        }
    }

}