Baekjoon11724-연결요소 개수

백준 사이트 11724- 연결요소 개수 문제입니다.

1. 문제

https://www.acmicpc.net/problem/11724

---

2. Input , Output

---

3. 분류 및 난이도

기초 BFS문제에서 결과값을 보존해야하는 변형 문제입니다.

---

4. 생각한 것들

• python으로 고치기 그냥 고치니까 시간초과가 뜹니다.

---

5. code

c++

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
bool check[1001] = { false, };
vector<int>* vec;
int bfs(int start)
{
	if (check[start] == true)
		return 0;
	queue<int> q;
	q.push(start);
	check[start] = true;
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 0; i < vec[x].size(); ++i)
		{
			int y = vec[x][i];
			if (!check[y])
			{
				q.push(y);
				check[y] = true;
			}
		}
	}
	return 1;
}

int main()
{
	int n, m;
	cin >> n>>m;

	vec = new vector<int>[n + 1];
	
	for (int i = 0; i < m; ++i)
	{
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	int result = 0;
	for (int i = 1; i <= n; ++i)
	{
		result +=bfs(i);
 	}
	cout << result;
	delete[]vec;

}

python

import sys
#BFS
from collections import deque

def BFS(graph, root,visited):
    if(visited[root]==1):
        return 0
    queue = deque([root])
    visited[root]=1
    while queue:
        n = queue.popleft()
        for i in range (len(graph[n])):
            y  = graph[n][i]
            if(y != 0 and visited[y]==0): 
                queue.append(y)
                visited[y]=1
    return 1


n,m = map(int,input().split())
graph = []
for i in range(n+1):
    line = []
    graph.append(line)
visited = [0] * (n+1) 
for i in range (0,m):
    first,second = map(int,input().split())
    graph[first].append(second)
    graph[second].append(first)
    
result = 0
for i in range (0,n+1):
    visited[i]=0
for i in range(1,n+1):
    result= result + BFS(graph,i,visited)
print(result)

---

6. 후기

python이랑 c++ 실행속도 차이 너무 체감이..

pypy3으로 제출해야겠다.