Cod sursa(job #3266150)

Utilizator lucky1992Ion Ion lucky1992 Data 6 ianuarie 2025 02:43:04
Problema Parcurgere DFS - componente conexe Scor 90
Compilator java Status done
Runda Arhiva educationala Marime 2.08 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, boolean[] hasVisited) {
    hasVisited[u] = true;
    List<Integer> neighbors = g.adj[u];
    if (neighbors != null) {
      for (int v : neighbors) {
        if (!hasVisited[v]) {
          dfsVisit(g, v, hasVisited);
        }
      }
    }
  }

  public static int dfs(UndirectedGraph g) {
    boolean[] hasVisited = new boolean[g.adj.length];
    Arrays.fill(hasVisited, false);
    Set<Integer> visited = new HashSet<>();
    int connectedComp = 0;
    for (int u = 1; u < g.adj.length; u++) {
      if (!hasVisited[u]) {
        dfsVisit(g, u, hasVisited);
        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));
  }
}