/*
Grafi

vozlišča = nodes, vertex (vertices)
povezave (usmerjene, neusmerjene) = edges (directed, undirected)

Graf G = (V, E), |V| = n, |E| = m
V = {1, 2, 3, 4, 5, 6}
E = {{1, 2}, {1, 5}, {5, 2}, {3, 2}, {4, 6}, {4, 5}, {4, 3}}

Usmerjeni / neusmerjeni
Uteženi (weighted) / neuteženi  -- uteži so lahko na povezavah ali na vozliščih
povezava iz vozlišča nase -- zanka (loop)
pot (path) -- zaporedje povezanih vozlišč brez ponavljanja
dolžina poti -- število povezav na poti
sprehod (walk) -- zaporedje povezanih vozlišč
cikel (cycle) -- sklenjena pot (zadnje vozlišče se ponovi)
(vhodna/izhodna) stopnja vozlišča ((in/out) degree) -- število povezav (v/iz) vozlišča, deg(v) = stopnja
sosedi od v -- množica vozlišč neposredno povezanih z v
v je dosegljiv iz u -- obstaja pot iz u do v
G je povezan (connected) -- obstaja pot od vsakega do vsakega vozlišča
komponenta grafa (component) -- množica vozlišč, ki so vsa medsebojno dosegljiva
sosedno vozlišče (adjancent vertex)

izrek: sum(deg(v) for v in V) == 2*len(E))

for v in V:
    for s in sosedi(v):
        f()
-> časovna zahtevnost: O(V) + O(E)*O(f())

razpon števila povezav: E \in [0, n*(n-1)/2], usmerjen: E \in [0, n*(n-1)], usmerjen z zankami: [0, n*n], povezan graf: [n-1, n*(n-1)/2]

drevo (tree): povezan graf brez ciklov (E == V-1), splošen graf brez ciklov = gozd (forest)

DAG (directed acyclic graph): klasičen primer: dependency graph

poln graf == graf z vsemi možnimi povezavami


# Predstavitev grafa:

seznam vozlišč, povezav:
V = [0, 1, 2, 3, 4, 5, 6, 7, 8]  (n = 9)
E = [(2, 3), (5, 6), (2, 1), ....]

ponavadi: seznam sosednosti (adjancency list)
n == len(G)
G = [[], [2], [3, 1], [2], [], [6], [5], [], []]

# zanka čez vse povezave:
for i in range(len(G)):
    for v in G[i]:
        // i ~ v je povezava

utežen graf: G = [[], [(2, 15.7)], [(3, ...) , (1, ...)], [2], [], [6], [5], [], []]

še ena možnost: matrika sosednosti (adjancency matrix)

G = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
]

*/

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <array>

using namespace std;

// int t = 0;
// iskanje v globino = depth first search
// Časovna zahtevnost: vsako vozlišče obiščemo enkrat, O(deg(v)) (gremo čez vse sosede)
// vse skupaj: O(V+E)
void dfs(int i, const vector<vector<int>>& G, vector<bool>& visited, vector<int>& component) {
    // ++t;
    // cout << "enter " << i << ", t = " << t << endl;
    visited[i] = true;
    component.push_back(i);
    for (int v : G[i]) {
        if (!visited[v]) {
            dfs(v, G, visited, component);
        }
    }
    // ++t;
    // cout << "exit " << i << ", t = " << t << endl;
}

// Iskanje v sirino (breadth first search)
// Časovna zahtevnost: vsako vozlišče obiščemo enkrat, O(deg(v)) (gremo čez vse sosede)
// vse skupaj: O(V+E)
void bfs(int i, const vector<vector<int>>& G, vector<bool>& visited, vector<int>& component) {
    visited[i] = true;
    queue<int> q({i});
    while (!q.empty()) {
        int c = q.front();
        q.pop();

        component.push_back(c);

        for (int v : G[c]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int pop(queue<int>& q) {
    int t = q.front();
    q.pop();
    return t;
}

int pop(stack<int>& s) {
    int t = s.top();
    s.pop();
    return t;
}

// Iskanje v sirino (breadth first search)
template <typename T>
void search(int i, const vector<vector<int>>& G, vector<bool>& visited, vector<int>& component) {
    visited[i] = true;
    T q({i});
    while (!q.empty()) {
        int c = pop(q);

        component.push_back(c);

        for (int v : G[c]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

array<pair<int, int>, 4> DIRS = {{{-1, 0}, {1, 0}, {0, 1}, {0, -1}}};

vector<string> pobarvaj(vector<string> slika, int i, int j, char c) {
    char old = slika[i][j];
    if (old == c) return slika;
    int h = slika.size();
    int w = slika[0].size();

    slika[i][j] = c;
    queue<pair<int, int>> q({{i, j}});
    while (!q.empty()) {
        auto [ci, cj] = q.front();
        q.pop();

        // Gremo čez sosede.
        for (auto [di, dj] : DIRS) {
            int ni = ci + di;
            int nj = cj + dj;
            if (0 <= ni && ni < h && 0 <= nj && nj < w && slika[ni][nj] == old) {
                slika[ni][nj] = c;
                q.push({ni, nj});
            }
        }
    }
    return slika;
}


int main() {
    vector<vector<int>> G = {{1, 2, 5}, {0, 2}, {1, 0}, {4}, {3}, {0}};
    int n = G.size();

    // int n = 1'000'000;
    // vector<vector<int>> G(n, vector<int>());
    // for (int i = 0; i < n; ++i) {
    //     int j = (i == n-1) ? 0 : i + 1;
    //     G[i].push_back(j);
    //     G[j].push_back(i);
    // }

    vector<bool> visited(n, false);
    vector<vector<int>> components;

    for (int i = 0; i < n; ++i) {
        if (visited[i]) continue;
        components.push_back({});
        // dfs(i, G, visited, components.back());
        bfs(i, G, visited, components.back());

        // search<queue<int>>(i, G, visited, components.back());
        // search<stack<int>>(i, G, visited, components.back());
    }

    for (auto cc : components) {
        for (int c : cc) {
            cout << c << ", ";
        }
        cout << endl;
    }
    // cout << components.size() << endl;


    vector<string> slika = {
        "xx..vv.n.",
        "xxvvv..n.",
        "..zzvvvn.",
        ".zccccc..",
    };
    auto res = pobarvaj(slika, 1, 4, '#');
    for (auto s : res) {
        cout << s << endl;
    }
    return 0;
}