Cod sursa(job #2004479)

Utilizator valentinoMoldovan Rares valentino Data 26 iulie 2017 00:40:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 2.67 kb
import java.io.*;
import java.util.*;

public class Main 
{
    public static void main(String[] args) throws IOException
    {
        MyScanner reader = new MyScanner("dfs.in");
        PrintWriter writer = new PrintWriter("dfs.out");
        
        int n = reader.nextInt();
        int m = reader.nextInt(); 
        int count = 0;
        
        List< Node< Integer > > graf = new ArrayList<>(100005);
        for(int i = 1; i <= n + 1; ++i) graf.add(new Node<>(i));
        
        for(int i = 1; i <= m; ++i)
        {
            int x = reader.nextInt();
            int y = reader.nextInt();
            
            Node< Integer > NodeX = graf.get(x);
            Node< Integer > NodeY = graf.get(y);   
            
            NodeX.neighbours.add(NodeY);
            NodeY.neighbours.add(NodeX);
            
        }
        
        int solution = -1;
        
        for(Node<Integer> i: graf)
        {
            if(!i.visited)
            {
                solution++;
                DFS(i);
            }
        }
        
        writer.println(solution);
        
        reader.close();
        writer.close();
        
        
    }  
    
    private static void DFS(Node<Integer> node)
    {
        node.visited = true;
        for(Node<Integer> i: node.neighbours)
        {
            if(!i.visited)
            {
                DFS(i);
            }
        }
    }
    
    private static class Node<T>
    {
        private T value;
        private boolean visited;
        private List< Node< Integer > > neighbours;
        
        public Node(T value)
        {
            this.value = value;
            this.visited = false;
            this.neighbours = new ArrayList<>();
        }
    }
    
    private static class MyScanner
    {
         private BufferedReader bufferedReader;
         private StringTokenizer stringTokenizer;
         
         MyScanner(String filename) throws FileNotFoundException
         {
             bufferedReader = new BufferedReader(new FileReader(filename));
         }
         
         private String next() throws IOException
         {
             while(stringTokenizer == null || !stringTokenizer.hasMoreElements())
             {
                 stringTokenizer = new StringTokenizer(bufferedReader.readLine());
             }
             return stringTokenizer.nextToken();
         }
         
         int nextInt() throws IOException
         {
             return Integer.parseInt( next() );
         }
         
         void close() throws IOException
         {
             bufferedReader.close();
         }
    }
}