11725번

11725번 - 트리의 부모 찾기

그래프가 주어지고 , 결국 트리의 노드를 1로 하라고 했기 때문에

DFS나 BFS를 이용하여 탐색하면서 부모 노드의 값만 저장해주면 될 것 같다.

발생한 문제점 

cout << numOfparent[i] << endl;  을 정답 출력시  사용하니까 시간제한에 걸렸다.

하지만 이를 

printf("%d\n", numOfparent[i]);

로 바꾸니 시간 안에 통과하여 AC를 받을 수 있었다.

cout<<endl; 이 속도가 조금 느리다는 것은 알았지만 이렇게 시간 제한에 걸리다니.....

1초라는 시간은 너무나 짧은 것 같다... 이것 때문에 시간 초과가 나는 지 모르고 시간을 낭비하다니.. 출력 방식을 바꿔야 하는지 의문이다..

질문 게시판에 글을 좀 올려놔야 겠다.

<정답 코드 - DFS , BFS ( 사용하지 않는 함수 주석처리)>

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int N;
int numOfparent[100001];
vector<int> v[100001];
bool check[100001];
void bfs(int start)
{
    queue<int> q;
    q.push(start);
    check[start] = true;
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i];
 
            if (!check[next])
            {
                check[next] = true;
                numOfparent[next] = now;
                q.push(next);
            }
        }
    }
}
void dfs(int start)
{
    check[start] = true;
 
    for (int i = 0; i < v[start].size(); i++)
    {
        int next = v[start][i];
 
        if (!check[next])
        {
            numOfparent[next] = start;
            dfs(next);
        }
    }
 
    return;
}
int main()
{
    cin >> N;
 
    for (int i = 0; i < N-1; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    //dfs(1);
    //bfs(1);
 
    for (int i = 2; i <= N; i++)
    {
        printf("%d\n", numOfparent[i]);
        //cout << numOfparent[i] << endl;
    }
 
    return 0;
}