Cod sursa(job #2755856)

Utilizator ilie_alex.petricaPetrica Ilie-Alex ilie_alex.petrica Data 28 mai 2021 16:11:11
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.18 kb
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class conexe{
	static class Task {
		public static final String INPUT_FILE = "dfs.in";
		public static final String OUTPUT_FILE = "dfs.out";

		// numarul maxim de noduri
		public static final int NMAX = (int)1e5 + 5; // 10^5 + 5 = 100.005

		// n = numar de noduri, m = numar de muchii/arce
		int n, m;

		// adj[node] = lista de adiacenta a nodului node
		// exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
		@SuppressWarnings("unchecked")
		ArrayList<Integer> adj[] = new ArrayList[NMAX];

		public void solve() {
			readInput();
			writeOutput(getResult());
		}

		private void readInput() {
			try {
				Scanner sc = new Scanner(new BufferedReader(new FileReader(
						INPUT_FILE)));
				n = sc.nextInt();
				m = sc.nextInt();

				for (int node = 1; node <= n; node++) {
					adj[node] = new ArrayList<>();
				}

				for (int i = 1, x, y; i <= m; i++) {
					// arc (x, y)
					x = sc.nextInt();
					y = sc.nextInt();
					adj[x].add(y);
					adj[y].add(x);
				}

				sc.close();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}

		private void writeOutput(int n) {
			try {
				PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
						OUTPUT_FILE)));
					pw.printf("%d ", n);
				pw.printf("\n");
				pw.close();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}

		private int getResult() {
			// TODO: Faceti sortarea topologica a grafului stocat cu liste de adiacenta din adj.
			// *******
			// ATENTIE: nodurile sunt indexate de la 1 la n.
			// *******

			int counter = 0;

			boolean []used = new boolean[n + 1];

			for (int i = 1; i <= n; i++)
				if (!used[i]) {
					dfs(i, used);
					counter++;
				}

			return counter;
		}
		private void dfs(int node, boolean []used) {
			used[node] = true;

			for (Integer val : adj[node])
				if (!used[val])
					dfs(val, used);


		}
	}

	public static void main(String[] args) {
		new Task().solve();
	}
}