11724-연결 요소의 개수 (오답)

 

11724번: 연결 요소의 개수

 

6 8 -> 정점의 수와 간선

1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

그래프에 위 노드를 생성하고 [{1,2},{2,5}...] 방문했는지 확인하는 visited[간선] 를 만들었다

 visited[M][M] 으로 만들지 않은 이유는 어자피 [0][0] 과  [0][1] 은 이어져있으니 같이 방문하기 때문에

for문을 돌면서 각 간선의 방문여부를 확인한다. 

만약 방문안했다면 bfs에서 그래프[i][1] 의 수와 같은 숫자를 그래프에서 for문으로 찾는다

이런식으로 [0][1] 에서 [1][0]으로 이동한다

1 2 
2 5
5 1

...

만약 더이상 이동할 곳이 없으면 sum++

 

 

 

public class B11724 {
    static int N,M;
    static int[][] graph;
    static boolean[] visited;



    static void bfs(int node){
        Queue<Integer> queue =  new LinkedList<>();
        visited[node] = true;
        queue.add(node);

        while(!queue.isEmpty()){
            int temp = queue.remove();

            visited[temp] = true;
            for(int i=0; i<M; i++) {
                if(graph[temp][1] == graph[i][0] && visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        int sum =0;
        graph = new int[M][2];
        visited = new boolean[M];

        for(int i=0; i<M; i++){
            for(int j=0; j<2; j++){
                graph[i][j] = sc.nextInt();
            }
        }

        for(int i=0; i<M; i++){
            if(visited[i]) continue;
            bfs(i);
            sum++;
        }
        System.out.println(sum);
    }
}

 

 

제출했더니 시간초과가 떴다

다른방법을 찾아봐야겠다