Pagini recente » Cod sursa (job #2134088) | Cod sursa (job #1138472) | Cod sursa (job #1658826) | Cod sursa (job #121442) | Cod sursa (job #3354646)
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
class MyScanner2 {
private BufferedReader br;
private StringTokenizer st;
public MyScanner2(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());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
public String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
public class Main {
public void parcurgere(ArrayList<Integer>[] graph, int[] state, Integer source)
{
state[source] = 1;
for (Integer v : graph[source])
{
if (state[v] == 0)
parcurgere(graph, state, v);
}
state[source] = 2;
}
public static void main(String[] args) throws IOException {
MyScanner2 scanner = new MyScanner2(new FileReader("dfs.in"));
Main obj = new Main();
int n, m;
n = scanner.nextInt();
m = scanner.nextInt();
ArrayList<Integer>[] graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++)
{
graph[i] = new ArrayList<>();
}
for (int i = 1; i <= m; i++)
{
int a = scanner.nextInt();
int b = scanner.nextInt();
graph[a].add(b);
graph[b].add(a);
}
int[] state = new int[n + 1]; //0 - not visited, 1 - in process, 2 - processed
Arrays.fill(state, 0);
int comp = 0;
for (int i = 1; i <= n; i++)
{
if (state[i] == 0)
{
comp++;
obj.parcurgere(graph, state, i);
}
}
try (BufferedWriter writer = new BufferedWriter(new FileWriter("dfs.out"))) {
writer.write(String.valueOf(comp));
}
}
}