Pagini recente » Cod sursa (job #2866684) | Cod sursa (job #433088) | Cod sursa (job #1570629) | Cod sursa (job #1947570) | Cod sursa (job #1450895)
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;
class DFS {
BufferedReader in;
PrintWriter out;
int m, n;
ArrayList<ArrayList<Integer>> graph;
boolean[] visited;
public void read() throws IOException {
in = new BufferedReader(new InputStreamReader(new FileInputStream("dfs.in")));
Scanner inInt = new Scanner(in);
n = inInt.nextInt();
m = inInt.nextInt();
graph = new ArrayList<ArrayList<Integer>>(n+1);
visited = new boolean[n+1];
for(int i = 0; i <= n; i++) {
graph.add(i, new ArrayList<Integer>());
}
int x, y;
for(int i = 0; i < m; i++) {
x = inInt.nextInt();
y = inInt.nextInt();
graph.get(x).add(y);
graph.get(y).add(x);
}
inInt.close();
in.close();
}
public void write(int components) throws FileNotFoundException {
out = new PrintWriter(new FileOutputStream ("dfs.out"));
/*out.println(n + " " + m);
for(int i = 1; i <= n; i++) {
ArrayList<Integer> list = graph.get(i);
for(int j = 0; j < list.size(); j++) {
out.println(i + " " + list.get(j));
}
}*/
out.println(components);
out.close();
}
public void myDFS(int x) {
visited[x] = true;
ArrayList<Integer> list = graph.get(x);
for(int i = 0; i < list.size(); i++) {
if(visited[list.get(i)] == false) {
myDFS(list.get(i));
}
}
}
public int components() {
int p = 0;
for(int i = 1; i <= n; i++) {
if(visited[i] == false) {
p++;
myDFS(i);
}
}
return p;
}
public static void main(String args[]) {
try {
DFS dfs = new DFS();
dfs.read();
dfs.write(dfs.components());
} catch(IOException e) {
e.printStackTrace();
}
}
}