Pagini recente » Cod sursa (job #122300) | Cod sursa (job #1139752) | Cod sursa (job #3037894) | Cod sursa (job #2160784) | Cod sursa (job #3181824)
import org.example.Bfs;
import java.io.*;
import java.util.*;
public class Main {
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader()
{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException
{
din = new DataInputStream(
new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException
{
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n') {
if (cnt != 0) {
break;
}
else {
continue;
}
}
buf[cnt++] = (byte)c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException
{
int ret = 0;
byte c = read();
while (c <= ' ') {
c = read();
}
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException
{
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException
{
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException
{
bytesRead = din.read(buffer, bufferPointer = 0,
BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException
{
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
public static void main(String[] args) throws IOException {
Reader scanner = new Reader("dfs.in");
int n = scanner.nextInt();
int m = scanner.nextInt();
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < m; i++) {
int from = scanner.nextInt();
int to = scanner.nextInt();
if (!graph.containsKey(from)) {
graph.put(from, new ArrayList<>());
}
graph.get(from).add(to);
if (!graph.containsKey(to)) {
graph.put(to, new ArrayList<>());
}
graph.get(to).add(from);
}
boolean[] visited = new boolean[n+1];
int res = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
res++;
dfs(graph, visited, i);
}
}
FileWriter fileWriter = new FileWriter("dfs.out");
PrintWriter printWriter = new PrintWriter(fileWriter);
printWriter.write("" + res);
printWriter.close();
}
private static void dfs(Map<Integer, List<Integer>> graph, boolean[] visited, int curr) {
visited[curr] = true;
for (var next : graph.getOrDefault(curr, List.of())) {
if (!visited[next]) {
dfs(graph, visited, next);
}
}
}
}