[코드포스 Practice18] D. Mr. Kitayuta's Colorful Graph

으으으 트리

아직 트리가 너무 낯설고 어려움

 

트리 응용해서 뭘 하는 것 같은데 모르겠다

 

트리가 아니라 그래프!

어제 계산이론 수업에 트리 나와서 안다.

 

트리의 정의

1. 사이클이 없어야 한다

2. 루트노드가 있다

3. 루트노드 에서 다른 노드로 가는 루트가 오직 하나여야 한다. 

 

예아

 

https://burningjeong.tistory.com/196?category=852372

Union-find (disjoint set)

 

색깔별로 그래프 만들어서 DFS 돌리기 / Union find로 만들기 두 가지로 할 수 있는데 두 가지로 다 해보려 한다흑흑

 

그래프... 익숙해져야지

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;

vector<int> parent[101];

void    init(int n)
{
    for (int i = 1; i <= 100; i++)
        parent[i].resize(n+1);

    for (int j = 1; j <= 100; j++)
    {
        for (int i = 1; i <= n; i++)
            parent[j][i] = i;
    }
}

int     find(int x, int c)
{
    if (x == parent[c][x])
        return x;
        
    return parent[c][x] = find (parent[c][x], c);
}

void    merge(int x, int y, int c)
{
    x = find(x, c);
    y = find(y, c);
    
    parent[c][x] = y;
}

int     main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    init(n);
    
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        merge(a, b, c);
    }
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        
        int count = 0;
        for (int j = 1; j <= 100; j++)
        {
            if (find(u, j) == find(v, j))
                count++;
        }
        cout << count << endl;
    }
    
    return 0;
}

 

Union find... 끝...

얜 할만했음 (일단 코드가 간단하기도 하고)

 

이제 DFS ...!

https://burningjeong.tistory.com/208?category=852372

DFS 깊이 우선 탐색

 

DFS는 왜이렇게 어렵지???? 누가 DFS 만들었어

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;

vector<int> edge[101][10005];
bool visited[101][10005];

bool    dfs(int x, int y, int c)
{
    if (x == y)
        return true;
    
    if (visited[c][x])
        return false;
    
    visited[c][x] = true;
    
    for (auto& nxt : edge[c][x])
    {
        if (dfs(nxt, y, c))
            return true;
    }
    
    return false;
}

void    reset(int c)
{
    for (int i = 0; i < 10005; i++)
    {
        visited[c][i] = false;
    }
}

int     main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        edge[c][a].push_back(b);
        edge[c][b].push_back(a);
    }
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        int count = 0;
        for (int j = 1; j <= 100; j++)
        {
            reset(j);
            if(dfs(u, v, j))
                count++;
        }
        cout << count << endl;
    }
    
    return 0;
}