Cod sursa(job #2831404)

Utilizator Artick5Andrei Artick5 Data 11 ianuarie 2022 12:33:27
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.32 kb
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();
	}
}