Pagini recente » Cod sursa (job #1903866) | Cod sursa (job #2889475) | Cod sursa (job #1223595) | Cod sursa (job #326874) | Cod sursa (job #1705151)
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class Main {
public static void main(String[] args) throws FileNotFoundException, IOException {
BufferedReader in = new BufferedReader(new FileReader("dfs.in"));
String temp[] = in.readLine().split(" ");
int N = Integer.parseInt(temp[0]);
int M = Integer.parseInt(temp[1]);
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i <= N; i++) {
g.add(i, new ArrayList<Integer>());
}
for (int i = 0; i < M; i++) {
temp = in.readLine().split(" ");
int x = Integer.parseInt(temp[0]);
int y = Integer.parseInt(temp[1]);
g.get(x).add(y);
}
vis = new int[N + 1];
dfs(g);
PrintWriter out = new PrintWriter("dfs.out");
int cnx = 0;
for (int i = 1; i <= N; i++) {
if (vis[i] != 0) {
cnx++;
}
}
System.out.println(cnx);
out.print(cnx);
in.close();
out.close();
}
static int[] vis;
static void dfs(List<List<Integer>> g) {
for (int i = 1; i < g.size(); i++) {
if (vis[i] == 0) {
Stack<Integer> s = new Stack<Integer>();
s.push(i);
while (!s.isEmpty()) {
int j = s.pop();
for (Integer n : g.get(j)) {
if (vis[n] == 0) {
vis[n] = j;
s.push(n);
}
}
}
}
}
}
}