Pagini recente » Cod sursa (job #863925) | Cod sursa (job #1430907) | Istoria paginii utilizator/cergan.naomi | Cod sursa (job #1298193) | Cod sursa (job #1430893)
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class Main {
static ArrayList<ArrayList<Integer>> list;
static int n;
static int [] visited;
public Main(int n){
this.n = n;
list = new ArrayList<ArrayList<Integer>>(n+1);
for (int i = 0; i <= n; i++) {
list.add(new ArrayList<Integer>());
}
visited = new int[n+1];
}
static void dfs(int source){
visited[source] = 1;
for (int i = 0; i < list.get(source).size(); i++) {
if(visited[list.get(source).get(i)] == 0){
// System.out.println("Am gasit nevizitat " + i);
dfs(list.get(source).get(i));
}
}
}
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new FileReader("dfs.in"));
int n =in.nextInt();
int m = in.nextInt();
int k=0,x,y;
Main main = new Main(n);
for (int i = 0; i < m; i++) {
x = in.nextInt();
y = in.nextInt();
list.get(x).add(y);
list.get(y).add(x);
}
in.close();
for (int i = 1; i <= n; i++) {
if(visited[i] == 0){
// System.out.println("Parcurg din: " + i);
dfs(i);
k++;
}
}
BufferedWriter out = new BufferedWriter(new FileWriter("dfs.out"));
out.append(k + "\n");
out.close();
}
}