Cod sursa(job #2090164)

Utilizator abitlazyabitlazy abitlazy Data 17 decembrie 2017 17:45:53
Problema Parcurgere DFS - componente conexe Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 1.58 kb
import java.io.*;
import java.util.*;

public class Main {
	private static final String INPUT_FILE_PATH = "dfs.in";
	private static final String OUTPUT_FILE_PATH = "dfs.out";

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(new FileReader(INPUT_FILE_PATH));
		PrintWriter out = new PrintWriter(OUTPUT_FILE_PATH);
		int n = in.nextInt();
		int m = in.nextInt();
		UndirectedGraph mGraph = new UndirectedGraph(n);
		while (m-- > 0) {
			int source = in.nextInt();
			int dest = in.nextInt();
			mGraph.addEdge(source, dest);
		}
		out.print(mGraph.countConnectedComponents());
		out.flush();
		in.close();
		out.close();
	}

	static class UndirectedGraph {
		private List<List<Integer>> adjList;
		private int cntNodes;
		private boolean[] isReached;

		public UndirectedGraph(int n) {
			this.cntNodes = n;
			this.adjList = new ArrayList<>();
			for (int i = 0; i <= n; ++i) {
				this.adjList.add(new ArrayList<Integer>());
			}
			this.isReached = new boolean[n + 1];
			Arrays.fill(isReached, false);
		}

		public void addEdge(int source, int dest) {
			this.adjList.get(source).add(dest);
			this.adjList.get(dest).add(source);
		}

		public int countConnectedComponents() {
			int cnt = 0;
			Arrays.fill(isReached, false);
			for (int i = 1; i <= this.cntNodes; ++i) {
				if (!isReached[i]) {
					dfs(i);
					++cnt;
				}
			}
			return cnt;
		}

		private void dfs(int i) {
			this.isReached[i] = true;
			List<Integer> neighbList = this.adjList.get(i);
			for (int neighbor : neighbList) {
				if (!isReached[neighbor]) {
					dfs(neighbor);
				}
			}
		}
	}

}