Pagini recente » Cod sursa (job #2385876) | Cod sursa (job #95900) | Cod sursa (job #3226726) | Cod sursa (job #1672926) | Cod sursa (job #3224962)
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.ArrayList;
import java.util.Scanner;
public class Main {
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 muchia (node, neigh)
@SuppressWarnings("unchecked")
ArrayList<Integer> adj[] = new ArrayList[NMAX];
// nodul sursa in parcurgerea BFS
int conex;
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();
//source = sc.nextInt();
for (int node = 1; node <= n; node++) {
adj[node] = new ArrayList<>();
}
for (int i = 1, x, y; i <= m; i++) {
// muchie (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 conex) {
try {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
OUTPUT_FILE)));
pw.printf("%d", conex);
pw.close();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private int getResult() {
int conexCount = 0;
boolean[] visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i, visited);
conexCount++;
}
}
return conexCount;
}
private void dfs(int node, boolean[] visited) {
visited[node] = true;
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
dfs(neighbor, visited);
}
}
}
}
public static void main(String[] args) {
new Task().solve();
}
}