Pagini recente » Cod sursa (job #872950) | Cod sursa (job #2315424) | Cod sursa (job #1073492) | Cod sursa (job #1165969) | Cod sursa (job #2755856)
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();
}
}