---
# System prepended metadata

title: 'korki: union-find i djikstra'

---

# korki: union-find i djikstra
```cpp=
#include<iostream>
#include<queue>
#include<stack>

#define MAX_D 2147483647

int main(){
    int N;
    // algorytm djikstry w 0
    int dist[N];
    int visited[N];
    
    vector<vector<int>> neighbors(N);
    
    stack<int> next();
    for(int i = 0; i < N; i++){
        dist[i] = MAX_D;
        visited[i] = 0;
    }
    next.push(0);
    
    while(!next.is_empty()){
        int current = next.top();
        next.pop();
        visited[current] = true;
        
        for(auto (neighbor, weight) : neighbors[current]){
            // aktualizuj droge do nehigbor przez current
            // jezeli sie oplaca
            
            if(dist[current] + weight < dist[neighbor]){
                dist[neighbor] = dist[current] + weight;
            }
            if(!visited[neighbor])
                next.push(neighbor);
        }
    }
    
}
```


```cpp=
#include<iostream>

using namespace std;

int rep_find(int rep[], int v){
    int u = rep[v];
    if(u==v)
        return v;
    rep[v] = rep_find(rep, u);
    return rep[v];
}

void rep_union(int rep[], int v, int u){
    // ustawiamy reprezentant u na reprezentanta v
    v = rep_find(rep, v);
    u = rep_find(rep, u);
    rep[u] = v;
}


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

    int rep[n];
    for(int i = 0; i < n; i++){
        rep[i] = i;
    }

    for(int i = 0; i < m; i++){
        int v, u;
        cin >> v >> u;
        if(v != u)
            rep_union(rep, v-1, u-1);
    }


    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        int v, u;
        cin >> v >> u;
        v = rep_find(rep, v - 1);
        u = rep_find(rep, u - 1);
                
        cout << (v == u ? "TAK" : "NIE") << '\n';
    }
}

```