Pagini recente » Cod sursa (job #1546844) | Cod sursa (job #1534170) | Cod sursa (job #2533735) | Istoria paginii runda/simulare2016_lasm | Cod sursa (job #1239748)
import java.io.*;
import java.util.*;
class FastScanner {
private BufferedReader br;
private StringTokenizer st;
public FastScanner(InputStream stream) {
br = new BufferedReader(new InputStreamReader(stream));
}
private String next() {
while (st == null || !st.hasMoreTokens()) {
String line = null;
try {
line = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
if (line == null)
return null;
st = new StringTokenizer(line);
}
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 class Main {
private static List<List<Integer>> G;
private static int V;
private static boolean[] Visited;
private static void DFS(final int x) {
Visited[x] = true;
for (int y: G.get(x))
if (!Visited[y])
DFS(y);
}
private static void addEdge(final int x, final int y) {
G.get(x).add(y);
G.get(y).add(x);
}
public static void main(String[] args) throws IOException {
FastScanner reader = new FastScanner(new FileInputStream("dfs.in"));
V = reader.nextInt();
G = new ArrayList<List<Integer>>(V);
for (int x = 0; x < V; ++x)
G.add(new ArrayList<Integer>());
int edgeCount = reader.nextInt();
for (; edgeCount > 0; --edgeCount) {
int x = reader.nextInt() - 1;
int y = reader.nextInt() - 1;
addEdge(x, y);
}
Visited = new boolean[V];
int componentCount = 0;
for (int x = 0; x < V; ++x) {
if (!Visited[x]) {
++componentCount;
DFS(x);
}
}
PrintWriter writer = new PrintWriter("dfs.out");
writer.write(componentCount + "\n");
writer.close();
}
}