Cod sursa(job #2679585)

Utilizator mstevanStevan mstevan Data 30 noiembrie 2020 22:10:07
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.75 kb
package com.company;

import java.util.*;
import java.io.*;

public class Dfs {
    private static int n;
    private static int m;
    private static ArrayList<Integer> [] graph;
    private static boolean [] visited;
    private static int count;

    public static void main(String []args) {
        File inputFile = new File("dfs.in");
        File outputFile = new File("dfs.out");

        try {
            FileInputStream inputStream = new FileInputStream(inputFile);
            Scanner scanner = new Scanner(inputStream);
            n = scanner.nextInt(); // number of nodes - how many lists
            m = scanner.nextInt(); // number of edges - how many rows
            graph = new ArrayList[n];
            visited = new boolean [n];
            for (int i = 0; i < n; i++){
                graph[i] = new ArrayList<Integer>();
            }

            for (int i = 0; i < m; i++){
                int x = scanner.nextInt();
                int y = scanner.nextInt();
                graph[x - 1].add(y - 1);
                graph[y - 1].add(x - 1);
            }

            inputStream.close();

            for (int i = 0; i < n; i++){
                if (!visited[i]){
                    traverse(i);
                    count++;
                }
            }

            FileOutputStream outputStream = new FileOutputStream(outputFile);
            PrintWriter writer = new PrintWriter(outputStream);
            writer.println(count);

            writer.close();
            outputStream.close();
        } catch(IOException e) {

        }
    }

    private static void traverse(int i) {
        visited[i] = true;
        for (int adjacentNode: graph[i]) {
            if (!visited[adjacentNode])
                traverse(adjacentNode);
        }
    }
}