Cod sursa(job #3266147)

Utilizator lucky1992Ion Ion lucky1992 Data 6 ianuarie 2025 01:12:18
Problema Parcurgere DFS - componente conexe Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 1.98 kb
import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {

  private 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 ArrayList<>(32);
      }

      adj[u].add(v);

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

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

  private static void dfsVisit(UndirectedGraph g, int u, Map<Integer, Integer> parent) {
    List<Integer> neighbors = g.adj[u];
    if (neighbors != null) {
      for (int v : neighbors) {
        if (!parent.containsKey(v)) {
          parent.put(v, u);
          dfsVisit(g, v, parent);
        }
      }
    }
  }

  public static int dfs(UndirectedGraph g) {
    Map<Integer, Integer> parent = new HashMap<>();
    int connectedComp = 0;
    for (int u = 1; u < g.adj.length; u++) {
      if (!parent.containsKey(u)) {
        parent.put(u, -1);
        dfsVisit(g, u, parent);
        connectedComp++;
      }
    }
    return connectedComp;
  }

  public static void main(String[] args) throws IOException {
    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));


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