Pagini recente » Cod sursa (job #1212299) | Cod sursa (job #821800) | Cod sursa (job #900516) | Cod sursa (job #1489873) | Cod sursa (job #2831404)
import java.io.File;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;
public class ComponenteConexe
{
private static void dfs(int i, boolean[] visited, ArrayList<Integer>[] adj)
{
visited[i] = true;
for(int v : adj[i])
{
if(!visited[v])
{
dfs(v, visited, adj);
}
}
}
private static int solve(ArrayList<Integer>[] adj)
{
int componentNum = 0;
boolean[] visited = new boolean[adj.length];
for(int i = 1; i < adj.length; i++)
{
if(!visited[i])
{
dfs(i, visited, adj);
componentNum = componentNum + 1;
}
}
return componentNum;
}
public static void main(String[] args) throws java.io.FileNotFoundException
{
Scanner scanner = new Scanner(new File("dfs.in"));
int n = scanner.nextInt();
int m = scanner.nextInt();
ArrayList<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[n + 1];
for (int i = 1; i < n + 1; i++)
{
adj[i] = new ArrayList<Integer>();
}
for (int i = 0; i < m; i++)
{
int x, y;
x = scanner.nextInt();
y = scanner.nextInt();
adj[x].add(y);
adj[y].add(x);
}
PrintWriter p = new PrintWriter("dfs.out");
p.println(solve(adj));
p.close();
}
}