Cod sursa(job #1705154)

Utilizator greenroFlorin Calota greenro Data 19 mai 2016 23:50:28
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.87 kb
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Main {

    public static void main(String[] args) throws FileNotFoundException, IOException {
        BufferedReader in = new BufferedReader(new FileReader("dfs.in"));
        String temp[] = in.readLine().split(" ");
        int N = Integer.parseInt(temp[0]);
        int M = Integer.parseInt(temp[1]);
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            g.add(i, new ArrayList<Integer>());
        }
        for (int i = 0; i < M; i++) {
            temp = in.readLine().split(" ");
            int x = Integer.parseInt(temp[0]);
            int y = Integer.parseInt(temp[1]);
            g.get(x).add(y);
            g.get(y).add(x);
        }
        vis = new int[N + 1];
        dfs(g);
        PrintWriter out = new PrintWriter("dfs.out");
        int cnx = 0;
        for (int i = 1; i <= N; i++) {
            if (vis[i] != 0) {
                cnx++;
            }
        }
        System.out.println(cnx);
        out.print(cnx);
        in.close();
        out.close();
    }

    static int[] vis;

    static void dfs(List<List<Integer>> g) {
        for (int i = 1; i < g.size(); i++) {
            if (vis[i] == 0) {
                Stack<Integer> s = new Stack<Integer>();
                s.push(i);
                while (!s.isEmpty()) {
                    int j = s.pop();
                    for (Integer n : g.get(j)) {
                        if (vis[n] == 0) {
                            vis[n] = j;
                            s.push(n);
                        }
                    }
                }
            }
        }
    }
}