Pagini recente » Clasament | Cod sursa (job #2482056) | Cod sursa (job #3224963)
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.io.Reader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
private static class MyScanner {
private BufferedReader br;
private StringTokenizer st;
public MyScanner(Reader reader) {
br = new BufferedReader(reader);
}
public String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
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 {
MyScanner sc = new MyScanner(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);
}
} 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();
}
}