Cod sursa(job #3266149)

Utilizator lucky1992Ion Ion lucky1992 Data 6 ianuarie 2025 01:27:45
Problema Parcurgere DFS - componente conexe Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 2.02 kb
import java.io.*;
import java.util.*;

public class Main {

  public static class UndirectedGraph {

    private List<Integer>[] adj;

    public UndirectedGraph(int nodes) {
      adj = (List<Integer>[]) new List[nodes + 1];
    }

    public void addEdge(int u, int v) {
      if (adj[u] == null) {
        adj[u] = new LinkedList<>();
      }

      adj[u].add(v);

      if (adj[v] == null) {
        adj[v] = new LinkedList<>();
      }

      adj[v].add(u);
    }
  }

  private static void dfsVisit(UndirectedGraph g, int u, Set<Integer> visited) {
    List<Integer> neighbors = g.adj[u];
    if (neighbors != null) {
      for (int v : neighbors) {
        if (!visited.contains(v)) {
          visited.add(v);
          dfsVisit(g, v, visited);
        }
      }
    }
  }

  public static int dfs(UndirectedGraph g) {
    Set<Integer> visited = new HashSet<>();
    int connectedComp = 0;
    for (int u = 1; u < g.adj.length; u++) {
      if (!visited.contains(u)) {
        visited.add(u);
        dfsVisit(g, u, visited);
        connectedComp++;
      }
    }
    return connectedComp;
  }

  public static void main(String[] args) throws IOException {
//    long start = System.currentTimeMillis();
    BufferedReader reader = new BufferedReader(new FileReader("dfs.in"));
    PrintWriter out = new PrintWriter(new OutputStreamWriter(new FileOutputStream("dfs.out"), "UTF-8"), true);

    String line = reader.readLine();
    String[] parts = line.split(" ");
    int N = Integer.parseInt(parts[0]);
    int M = Integer.parseInt(parts[1]);

    UndirectedGraph g = new UndirectedGraph(N);

    for (int i = 0; i < M; i++) {
      line = reader.readLine();
      parts = line.split(" ");
      g.addEdge(Integer.parseInt(parts[0]), Integer.parseInt(parts[1]));
    }

    out.println(dfs(g));
    out.close();
//    long now = System.currentTimeMillis();
//    System.out.println((now - start));


//    UndirectedGraph g = new UndirectedGraph(6);
//    g.addEdge(1, 2);
//    g.addEdge(1, 4);
//    g.addEdge(3, 5);
//    System.out.println(dfs(g));
  }
}