Pagini recente » Monitorul de evaluare | Cod sursa (job #173763) | Monitorul de evaluare | Istoria paginii utilizator/nenciugeorgel8b | Cod sursa (job #1980006)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
MyScanner in = new MyScanner("dfs.in");
PrintWriter out = new PrintWriter("dfs.out");
int n = in.nextInt();
int m = in.nextInt();
List<Node<Integer>> graph = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
graph.add(new Node<>(i));
}
for (int i = 0; i < m; i++) {
int u = in.nextInt() - 1;
int v = in.nextInt() - 1;
if (u == v) continue;
Node<Integer> nodeU = graph.get(u);
Node<Integer> nodeV = graph.get(v);
nodeU.neighbours.add(nodeV);
nodeV.neighbours.add(nodeU);
}
int count = 0;
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
count++;
DFS(graph.get(i), visited);
}
}
out.println(count);
out.close();
in.close();
}
private static int[] BFS(Node<Integer> s, int n) {
Queue<Node<Integer>> queue = new LinkedList<>();
int[] costs = new int[n];
Arrays.fill(costs, -1);
costs[s.value] = 0;
queue.add(s);
s.visited = true;
while (!queue.isEmpty()) {
Node<Integer> u = queue.poll();
for (Node<Integer> v : u.neighbours) {
if (!v.visited) {
costs[v.value] = costs[u.value] + 1;
v.visited = true;
queue.add(v);
}
}
}
return costs;
}
private static void DFS(Node<Integer> u, boolean[] visited) {
for (Node<Integer> v : u.neighbours) {
if (!visited[v.value]) {
visited[v.value] = true;
DFS(v, visited);
}
}
}
private static class Node<T> {
private T value;
private boolean visited;
private List<Node<Integer>> neighbours;
public Node(T value) {
this.value = value;
this.visited = false;
this.neighbours = new ArrayList<>();
}
}
private static class MyScanner {
private BufferedReader bufferedReader;
private StringTokenizer stringTokenizer;
MyScanner(String filename) throws FileNotFoundException {
bufferedReader = new BufferedReader(new FileReader(filename));
}
private String next() throws IOException {
while (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
}
return stringTokenizer.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
void close() throws IOException {
bufferedReader.close();
}
}
}