링크드 리스트 2

https://jaeyoon8783.tistory.com/6?category=876641

링크드 리스트

여기에서 링크드 리스트의 기본을 배웠다. 그런데 

 

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

11725번: 트리의 부모 찾기

트리를 DFS 탐색하는 과정에서 문제가 하나 발생했다.

go 함수(DFS 탐색) 중에 list를 다시 참조해야 하는데 list배열이 class List 위에 있으면 만들수가 없고 밑에 있으면 go함수가 참조 못하는 현상이 벌어진다. 

밑의 코드가 이런 예시이다. 안 돌아갈것이다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
 
int parent[100001];
class node
{
public :
    int data;
    node* next;
};
 
class List
{
public : 
    node* head = NULL;
    node* tail = NULL;
 
    void init(List l)
    {
        node* tmp = l.head;
 
        while (tmp != NULL)
        {
            head = tmp->next;
            delete tmp;
            tmp = head;
        }
        delete head;
 
    }
 
    void add(int data)
    {
        node* nnode = new node;
        nnode->data = data;
        nnode->next = NULL;
 
        if (head == NULL)
            head = nnode;
        else
            tail->next = nnode;
        tail = nnode;
    }
 
    
    void go(int cur, int p)
    {
        parent[cur] = p;
 
        node* tmp = head;
        while (tmp != NULL)
        {
            if (tmp->data != p)
                l[tmp->data].go(tmp->data, cur);
 
            tmp = tmp->next;
        }
 
    }
    
 
 
};
List l[100001];
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
    int n;
    cin >> n;
    int a, b;
    for (int i = 0; i < n-1; i++)
    {
        cin >> a >> b;
        l[a].add(b);
        l[b].add(a);
    }
 
    l[1].go(1, 0);
 
 
    for (int i = 2; i <= n; i++)
        cout << parent[i] << '\n';
 
}

그래서 List 배열과 

add, init, go 함수를 따로 나눠줘야 한다.

 

 

#include <iostream>
 
#define pii pair<int, int>
using namespace std;
 
int parent[100001];
class node
{
public :
    int data;
    node* next;
};
 
class List
{
public : 
    node* head = NULL;
    node* tail = NULL;
};
List list[100001];
 
 
void init(List list)
{
    node* tmp = list.head;
 
    while (tmp != NULL)
    {
        list.head = tmp->next;
        delete tmp;
        tmp = list.head;
    }
    delete list.head;
 
}
 
void add(int list_num, int data)
{
    node* nnode = new node;
    nnode->data = data;
    nnode->next = NULL;
 
    if (list[list_num].head == NULL)
        list[list_num].head = nnode;
    else
        list[list_num].tail->next = nnode;
    list[list_num].tail = nnode;
}
 
void go(int list_num, int cur, int p)
{
    parent[cur] = p;
    node* tmp = list[list_num].head;
 
    while (tmp != NULL)
    {
        if (tmp->data != p)
            go(tmp->data, tmp->data, cur);
        tmp = tmp->next;
    }
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
    int n;
    cin >> n;
    int a, b;
    for (int i = 0; i < n-1; i++)
    {
        cin >> a >> b;
 
        add(a, b);
        add(b, a);
    }
 
    //l[1].go(1, 0);
    go(1, 1, 0);
 
    for (int i = 2; i <= n; i++)
        cout << parent[i] << '\n';
 
}

이렇게 말이다.

 

20/08/20 추가..

 

인줄 알았는데 훨씬 더 간단하게 굳이 함수를 쓰지 않아도 되는것이였다.

 

 

#include <iostream>
#define pii pair<int, int>
using namespace std;
 
 
class node
{
public :
    int data;
    node* next;
};
 
class Edge
{
public :
    node* head = NULL;
    node* tail = NULL;
 
    void insert(int d)
    {
        node* nnode = new node;
        nnode->data = d;
        nnode->next = NULL;
 
        if (head == NULL)
            head = nnode;
        else
            tail->next = nnode;
        tail = nnode;
    }
};
Edge edge[100001];
int ans[100001];
 
void go(int cur, int parent)
{
    ans[cur] = parent;
 
    node* tmp = edge[cur].head;
 
    while (tmp != NULL)
    {
        if (tmp->data != parent)
            go(tmp->data, cur);
        tmp = tmp->next;
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int n,a,b;
    cin >> n;
 
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b;
        edge[a].insert(b);
        edge[b].insert(a);
    }
 
    go(1, 0);
 
    for (int i = 2; i <= n; i++)
        cout << ans[i] << '\n';
 
}