Cod sursa(job #3354646)

Utilizator Ciprian_AndreiHoza Ciprian-Andrei Ciprian_Andrei Data 19 mai 2026 16:58:06
Problema Parcurgere DFS - componente conexe Scor 90
Compilator java Status done
Runda Arhiva educationala Marime 2.45 kb
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

class MyScanner2 {
    private BufferedReader br;
    private StringTokenizer st;

    public MyScanner2(Reader reader) {
        br = new BufferedReader(reader);
    }

    public String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

public class Main {

    public void parcurgere(ArrayList<Integer>[] graph, int[] state, Integer source)
    {
        state[source] = 1;

        for (Integer v : graph[source])
        {
            if (state[v] == 0)
                parcurgere(graph, state, v);
        }

        state[source] = 2;
    }

    public static void main(String[] args) throws IOException {
        MyScanner2 scanner = new MyScanner2(new FileReader("dfs.in"));
        Main obj = new Main();

        int n, m;
        n = scanner.nextInt();
        m = scanner.nextInt();

        ArrayList<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++)
        {
            graph[i] = new ArrayList<>();
        }

        for (int i = 1; i <= m; i++)
        {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }

        int[] state = new int[n + 1]; //0 - not visited, 1 - in process, 2 - processed

        Arrays.fill(state, 0);
        int comp = 0;

        for (int i = 1; i <= n; i++)
        {
            if (state[i] == 0)
            {
                comp++;
                obj.parcurgere(graph, state, i);
            }
        }
        try (BufferedWriter writer = new BufferedWriter(new FileWriter("dfs.out"))) {
            writer.write(String.valueOf(comp));
        }
    }
}