Grafos

#include <bits/stdc++.h>

using namespace std;

enum{NOT_VISITED,VISITED};

using ii = pair<int,int>;
using vi = vector<int>;
using vii = vector<ii>;


/***
 * Lista de adjacências de um grafo. Cada aresta é representada com um par,
 * contendo o nó destino e o peso da aresta. No caso de grafos sem peso, o
 * segundo membro do par pode ser ignorado
 ***/
vector<vii> adj_list;

/***
 * dfs_num marca se um nó foi visitado ou não. Deve ser utilizado em uma
 * busca em profundidade para que ela não proceda a nós que já 
 * foram visitados de modo a evitar um laço infinito. Inicialmente,
 * deve ser inicializada com NOT_VISITED
 ***/
vi dfs_num;


/***
 * Busca em profundidade, parte de um nó u e, para cada vizinho não visitado,
 * faz a chamada recursiva para este vizinho.
 ***/
void dfs(int u){
    dfs_num[u] = VISITED;
    for(auto& v: adj_list[u]){
        if(dfs_num[v.first]==NOT_VISITED){
            dfs(v.first);
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

const int INFINITY{ numeric_limits<int>::max() };

using ii = pair<int,int>;
using vi = vector<int>;
using vii = vector<ii>;

/***
 * Estrutura que diz a distância para o nó de origem.
 * Inicialmente inicializada com Infinito;
 ***/

vi d;

/***
 * Lista de adjacências de um grafo. Cada aresta é representada com um par,
 * contendo o nó destino e o peso da aresta. No caso de grafos sem peso, o
 * segundo membro do par pode ser ignorado
 ***/
vector<vii> adj_list;



/***
 * Busca em largura partindo de um nó u. Inicialmente, visita-se
 * os vizinhos de u, depois os vizinhos dos vizinhos de u, e assim por diante.
 * Uma fila é utilizada para implementar este comportamento
 ***/
void bfs(int u){
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto& y: adj_list[x]){
            /** 
             * Se a distância até y.first é infinito, 
             * significa que ele não foi visitado 
             **/
            if(d[y.first]==INFINITY){
                d[y.first] = d[x]+1;
                q.push(y.first);
            }
        }
    }
}

void connected_components(){
    int n = 1;
    for(size_t i=0;i<adj_list.size();i++){
        if(dfs_num[i]==NOT_VISITED){
            cout << "Component #" << n << ": ";
            dfs(i);
            n++;
            cout << endl;
        }
    }
}

void dfs(int u){
    cout << u << " "; // imprime-se um nó da i-ésima componente 
    dfs_num[u] = VISITED;
    for(auto& v: adj_list[u]){
        if(dfs_num[v.first]==NOT_VISITED){
            dfs(v.first);
        }
    }
}

/**
 * Coordenada das movimentações
 **/
int dr[] = {1,1,0,-1,-1,-1, 0, 1};
int dc[] = {0,1,1, 1, 0,-1,-1,-1};

/**
 * @brief Flood-fill em um tabuleiro RxC
 * @param r número da linha
 * @param c número da coluna
 * @param c1 caractere de água
 * @param c2 caractere a substituir o caractere da água
 * @return Retorna a área do lago formado a partir da célula (r,c)
 */
int floodfill(int r, int c, char c1, char c2) {
    // Se está fora do grid, a área é 0
    if (r < 0 || r >= R || c < 0 || c >= C) return 0;
    // Se a célula não é uma posição com água, a área é 0
    if (grid[r][c] != c1) return 0;
    // Caso contrário já temos área do lago igual a 1
    int ans = 1;
    // Marca a posição (r,c) como visitada
    grid[r][c] = c2;
    // Aplica a busca em profundidade (flood-fill) nas adjacências
    for (int d = 0; d < 8; d++)
        ans += floodfill(r + dr[d], c + dc[d], c1, c2);
    // Retorna a área total do lago
    return ans;
}

#include <bits/stdc++.h>

using namespace std;

enum{NOT_VISITED,VISITED};

using ii = pair<int,int>;
using vi = vector<int>;
using vii = vector<ii>;


/***
 * Lista de adjacências de um grafo. Cada aresta é representada com um par,
 * contendo o nó destino e o peso da aresta. No caso de grafos sem peso, o
 * segundo membro do par pode ser ignorado
 ***/
vector<vii> adj_list;

/***
 * dfs_num marca se um nó foi visitado ou não. Deve ser utilizado em uma
 * busca em profundidade para que ela não proceda a nós que já 
 * foram visitados de modo a evitar um laço infinito. Inicialmente,
 * deve ser inicializada com NOT_VISITED
 ***/
vi dfs_num;


/**
 * tp é o vetor contendo a ordem dos vértices segundo a ordenação
 * topológica
 **/
vi tp;


/***
 * Busca em profundidade, parte de um nó u e, para cada vizinho não visitado,
 * faz a chamada recursiva para este vizinho.
 ***/
void dfs(int u){
    dfs_num[u] = VISITED;
    for(auto& v: adj_list[u]){
        if(dfs_num[v.first]==NOT_VISITED){
            dfs(v.first);
        }
    }
    tp.push_back(u);
}

// reverse(tp.begin(),tp.end()) 

#include <bits/stdc++.h>

using namespace std;

enum{WHITE=-1,BLUE=0,RED=1};

using ii = pair<int,int>;
using vi = vector<int>;
using vii = vector<ii>;

/***
 * Estrutura que diz a cor do nó.
 * color[u] = -1 se u  é branco, isto é, não foi visitado.
 * color[u] = 0 se u é azul
 * color[u] = 1 se u é vermelho.
 * Inicialmente todos os nós são brancos
 ***/

vi color;

/***
 * Lista de adjacências de um grafo. Cada aresta é representada com um par,
 * contendo o nó destino e o peso da aresta. No caso de grafos sem peso, o
 * segundo membro do par pode ser ignorado
 ***/
vector<vii> adj_list;



/**
 * @brief Busca em largura partindo de um nó u para verificar se um 
 * grafo é bipartido.
 * 
 * @param u nó inicial
 * @return true se o grafo é bipartido
 * @return false se o grafo não é bipartido.
 */
bool bfs(int u){
    queue<int> q;
    // u é pintado de vermelho e colocado na fila0
    q.push(u);
    color[u] = RED;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto& y: adj_list[x]){
            /***
             * Se a cor do vizinho de x é branca, ele é pintado da cor
             * oposta de x
             ***/
            if(color[y.first]==WHITE){
                color[y.first] = 1-color[x];
                q.push(y.first);
            }
            /***
             * Se x e seu vizinho y tem a mesma cor, o grafo não
             * pode ser bipartido
             ***/
            else if(color[y.first]==color[u]){
                return false;
            }
        }
    }
    return true;
}

#include <bits/stdc++.h>

using namespace std;


using ii = pair<int,int>;
using vi = vector<int>;
using vii = vector<ii>;



enum{WHITE=0,GREY=1,BLACK=2};

// Variáveis globais

int dfs_n = 0; // Numeração da DFS
vector<vi> g; // Lista de adjacências
vi dfs_num; // Estrutura dfs_num
vi dfs_low; // Estrutura dfs_low
vi visited; // Marca o estado do vértice
stack<int> st; // Pilha para armazenar a componente fortemente conexa

/**
 * @brief A partir de um nó u, computa as componentes fortementes conexas
 * dos nós alcançáveis a partir de u
 * 
 * @param u Nó inicial.
 */
void scc(int u) {
    dfs_num[u] = dfs_low[u] = dfs_n;
    dfs_n++;
    // Marca o nó como em processamento
    visited[u] = GREY;
    // Insere o nó na pilha
    st.push(u);
    for (auto v : g[u]) {
        // Para cada aresta (u,v)
        if (visited[v] == WHITE) {
            // Se v não foi visitado, aplique o algoritmo recursivamente
            scc(v);
            // atualize o menor nó alcançável por u se preciso
            dfs_low[u] = min(dfs_low[u], dfs_low[v]);
        } else if (visited[v] == GREY) {
            /** Se v foi visitado, porém não finalizado, então existe uma
             * back-edge de u para v, correspondendo a um ciclo, logo
             * atualiza-se dfs_low com a numeração de DFS de v, caso 
             * necessário
             **/
            dfs_low[u] = min(dfs_low[u], dfs_num[v]);
        }
    }
    /**
     * Caso dfs_low[u] == dfs_num[u] então todos os nós pertencentes à
     * componente fortemente conexa de u estão na pilha.
     **/
    if (dfs_low[u] == dfs_num[u]) {
        int v;
        /** Imprime os nós que compartilham a mesma componente 
         * fortemente conexa de u.
         */
        do {
            v = st.top();
            st.pop();
		    visited[v] = BLACK;
            cout << v << " "; 
        } while (u != v);
        cout << endl;
    }
}

/**
 * @brief Aplica o algoritmo scc para cada nó não visitado
 */
void find_scc(){
    for(size_t i=0;i<g.size();i++){
        if(visited[i]==WHITE){
            scc(i);
        }
    }
}

#include <bits/stdc++.h>

using namespace std;


using ii = pair<int,int>;
using vi = vector<int>;
using vii = vector<ii>;



enum{NIL = -1, WHITE=0,GREY=1,BLACK=2};

// Variáveis globais

int dfs_n = 0; // Numeração da DFS
vector<vi> g; // Lista de adjacências
vi dfs_num; // Estrutura dfs_num
vi dfs_low; // Estrutura dfs_low
vi visited; // Marca o estado do vértice
vector<bool> articulation_vertex;  // Marca quais vértices são pontos de articulação
vi parent; // Marca quem são os pais de cada nó na árvore de DFS. Inicializado com NIL.

/**
 * @brief A partir de um nó u, computa os vértices de articulação 
 * que são alcançáveis a partir de u.
 * 
 * @param u Nó inicial.
 */
void dfs_ap(int u) {
    dfs_num[u] = dfs_low[u] = dfs_n;
    dfs_n++;
    // Marca u como visitado
    visited[u] = BLACK;
    // Número de vizinhos imediatos de u não visitados
    int children = 0;
    for (auto v : g[u]) {
        // Para cada aresta (u,v)
        if (visited[v] == WHITE) {
            // Se v não foi visitado, aplique o algoritmo recursivamente
            children++;
            parent[v] = u;
            dfs_ap(v);
            // atualize o menor nó alcançável por u se preciso
            dfs_low[u] = min(dfs_low[u], dfs_low[v]);

            /** Se u é a raiz da DFS e possui mais de um filho,
             * então u é um ponto de articulação
             */  
            if(parent[u] == NIL && children>1){
                articulation_vertex[u] = true;
            }
            /** Se u não é a raiz da DFS e o vértice com numeração mais
             * baixa alcançável por v é maior ou igual a numeração de u,
             * então u é um ponto de articulação.
             */
            if(parent[u] !=NIL  && dfs_low[v]>=dfs_num[u]){
                articulation_vertex[u] = true;
            }
            
        }
        /** Se v já foi visitado, então (u,v) é uma back-edge. Se
         * essa aresta não forma um ciclo imediato, então atualiza-se
         * low[u]
         */ 
        else if (v!=parent[u]) {
            dfs_low[u] = min(dfs_low[u], dfs_num[v]);
        }
    }
}

/**
 * @brief Aplica o algoritmo dfs_ap para cada nó não visitado
 */
void find_ap(){
    for(size_t i=0;i<g.size();i++){
        if(visited[i]==WHITE){
            dfs_ap(i);
        }
    }
    for(size_t i=0;i<g.size();i++){
        if(articulation_vertex[i]){
            cout << i << " is an articulation vertex\n";
        }
    }
}

#include <bits/stdc++.h>

using namespace std;


using ii = pair<int,int>;
using vi = vector<int>;
using vii = vector<ii>;



enum{NIL = -1, WHITE=0,GREY=1,BLACK=2};

// Variáveis globais

int dfs_n = 0; // Numeração da DFS
vector<vi> g; // Lista de adjacências
vi dfs_num; // Estrutura dfs_num
vi dfs_low; // Estrutura dfs_low
vi visited; // Marca o estado do vértice
vi parent; // Marca quem são os pais de cada nó na árvore de DFS. Inicializado com NIL.

/**
 * @brief A partir de um nó u, imprime as pontes que são alcancáveis
 * alcançáveis a partir de u.
 * 
 * @param u Nó inicial.
 */
void dfs_bd(int u) {
    dfs_num[u] = dfs_low[u] = dfs_n;
    dfs_n++;
    // Marca u como visitado
    visited[u] = BLACK;
    // Número de vizinhos imediatos de u não visitados
    int children = 0;
    for (auto v : g[u]) {
        // Para cada aresta (u,v)
        if (visited[v] == WHITE) {
            // Se v não foi visitado, aplique o algoritmo recursivamente
            children++;
            parent[v] = u;
            dfs_bd(v);
            // atualize o menor nó alcançável por u se preciso
            dfs_low[u] = min(dfs_low[u], dfs_low[v]);

            // Verifica se (u,v) é uma ponte
            if(parent[u] !=NIL  && dfs_low[v]>dfs_num[u]){
                cout << "(" << u << "," << v << ") is a bridge\n";
            }
            
        }
        /** Se v já foi visitado, então (u,v) é uma back-edge. Se
         * essa aresta não forma um ciclo imediato, então atualiza-se
         * low[u]
         */ 
        else if (v!=parent[u]) {
            dfs_low[u] = min(dfs_low[u], dfs_num[v]);
        }
    }
}

/**
 * @brief Aplica o algoritmo dfs_ap para cada nó não visitado
 */
void find_bridges(){
    for(size_t i=0;i<g.size();i++){
        if(visited[i]==WHITE){
            dfs_bd(i);
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

class union_find{
public:
    /**
     * @brief Construtor, inicializa as estruturas
     * rank e parent, além de colocar o parent[i] para
     * cada elemento i
     * 
     * @param n número de elementos
     */
    union_find(int n){
        rank.assign(n,0);
        parent.assign(n,0);
        for(int i=0;i<n;i++){
            parent[i] = i;
        }
    }
    /**
     * @brief Retorna o elemento representativo do conjunto em que i
     * se encontra. Utiliza os ponteiros dos pais para localizar o
     * elemento representativo enquanto adota a técnica de path-compression;
     * 
     * @param i elemento inicial
     * @return int elemento representativo do conjunto em que i se encontra
     */
    int find(int i){
        return (parent[i]==i) ? i : (parent[i] = find(parent[i]));
    }

    /**
     * @brief Une os conjuntos em que i e j se encontram ao fazer
     * o merge entre duas árvores.
     * 
     * @param i primeiro elemento
     * @param j segundo elemento
     */
    void union_set(int i,int j){
        // Procura os elementos representativos de i e j
        auto x = find(i);
        auto y = find(j);
        // Se i e j não fazem parte do mesmo conjunto, a união é feita
        if(x!=y){
            if(rank[x] > rank[y]){
                parent[y] = x;
            }
            else{
                parent[x] = y;
                if(rank[x]==rank[y]){
                    rank[y]++;
                }
            }
        }        
    }

    /**
     * @brief Verifica se i e j estão no mesmo conjunto
     * 
     * @param i primeiro elemento
     * @param j segundo elemento
     * @return true caso i e j estejam no mesmo conjunto
     * @return false caso contrário
     */
    bool is_same_set(int i,int j){
        return find(i) == find(j);
    }
private:
    vector<int> parent,rank;
};

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int,int>;


/**
 * @brief Aplica o método de kruskal sobre o grafo.
 * 
 * @param edges um vetor contendo um par (peso, aresta), indicando
 * o peso de cada aresta do grafo. Cada aresta por sua vez é identificada
 * usando um par de vértices
 * @param n número de vértices do grafo
 * @return int o peso da árvore espalhada mínima
 */
int kruskal(vector<pair<int,ii>>& edges, int n){
    int cost = 0;
    // Ordena pelo peso
    sort(edges.begin(),edges.end());
    // Cria uma estrutura de conjuntos disjuntos de tamanho n;
    union_find uf(n);
    // Para cada aresta em ordem crescente de peso
    for(size_t i=0;i<edges.size();i++){
        /***
         * Caso os vértices das arestas estejam em componentes
         * distintas, a aresta tem que estar na árvore espalhada
         * mínima
         */
        if(!uf.is_same_set(edges[i].second.first,edges[i].second.second)){
            // Adiciona o peso da aresta no custo da MST
            cost += edges[i].first;
            // Une os dois vértices em uma mesma componente conexa
            uf.union_set(edges[i].second.first,edges[i].second.second);
        }
    }
    return cost;
}

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int,int>;
using vii = vector<ii>;

// Grafo
vector<vii> g;
// Vetor que marca os nós que já foram processados
vector<bool> processed;


/**
 * @brief Processa um nó u
 * 
 * @param pq fila de prioridades
 * @param u nó a ser processado
 */
void process(priority_queue<ii>& pq,int u){
    // marca u como processado
    processed[u] = true;
    // para cada vizinho de u
    for(auto& v: g[u]){
        // se o vizinho v.first não foi processado
        if(!processed[v.first]){
            /*** 
             * Insira na fila de prioridades a negação do custo
             * da aresta e a negação do identificador do nó vizinho.
             * Utiliza-se a negação pois a priority_queue é uma heap
             * de máximo.
             */
            pq.push({-v.second,-v.first});
        }
    }
}

/**
 * @brief Algoritmo de Prim
 * 
 * @return int retorna o custo da árvore espalhada mínima
 */
int prim(){
    int cost = 0;
    // marca todos os nós como não processados
    processed.assign(g.size(),false);
    // declara uma fila de prioridades que dá o próximo nó com menor custo
    priority_queue<ii> pq;
    // Processa o primeiro nó
    process(pq,0);
    // Enquanto houver nós a serem processados
    while(!pq.empty()){
        // Obtém o próximo nó de menor custo
        ii front = pq.top();
        pq.pop();
        // Restaura o peso e o id do nó ao negá-los
        auto u = -front.second;
        auto w = -front.first;
        // Se o nó não foi processado
        if(!processed[u]){
            // adicione ele á MST
            cost+=w;
            // Processe o nó
            process(pq,u);
        }
    }
    return cost;
}

#include <bits/stdc++.h>

using namespace std;
using ii = pair<int,int>;
using vii = vector<ii>;

const int INF = numeric_limits<int>::max();

// Vetores de custo e processamento
vector<int> cost;
vector<bool> processed;

/**
 * @brief Dado um grafo g e um nó de partida u, calcula o vetor
 * cost, que contém o tamanho do menor caminho entre u e qualquer
 * outro vértice de g
 * 
 * @param g grafo
 * @param u nó de partida
 */
void dijkstra(vector<vii>& g,int u){
    // Inicializa o custo de todos os nós como infinito
    cost.assign(g.size(),INF);
    // Marca todos os nós como não processados
    processed.assign(g.size(),false);

    priority_queue<ii> pq;
    // O custo do nó de partida só pode ser zero
    cost[u] = 0;
    // Insere o nó de partida na fila de prioridades
    pq.push({-cost[u],u});

    // Enquanto houver nós a serem retirados da fila de prioridades
    while(!pq.empty()){
        // Obtém o próximo nó de menor custo
        int v = pq.top().second;
        // Remove o nó da fila de prioridades
        pq.pop();
        // Se o nó já foi processado, pule esta iteração
        if(processed[v]){ 
            continue;
        }
        // Marque o nó como processado
        processed[v] = true;
        
        /***
         * Para cada vizinho w de v, verifique a condição de relaxamento,
         * isto é, se o custo de u até w for maior do que o custo de u
         * até v mais o peso da aresta (v,w), atualize o custo de u até
         * w.
         ***/
        for(auto& w: g[v]){
            if(!processed[w.first] && cost[w.first] > cost[v]+w.second){
                cost[w.first] = cost[v] + w.second;
                /***
                 * Após a atualização, insira o nó w com o custo atualizado
                 * na fila de prioridades. Aqui inserimos a negação do custo
                 * pois por padrão, a fila de prioridades é uma heap de 
                 * máximo
                 ***/
                pq.push({-cost[w.first],w.first});
            }
        }
    }
}

#include <bits/stdc++.h>

using namespace std;
using ii = pair<int,int>;
using vii = vector<ii>;

/***
 * Dividimos por dois para evitar overflow na soma 
 * de um valor INF com um valor positivo.
 ***/
const int INF = numeric_limits<int>::max()/2;

vector<int> cost;

/**
 * @brief Aplica o método de Bellman-Ford no grafo g para calcular
 * o custo do menor caminho entre u e qualquer outro nó de g
 * 
 * @param g Grafo
 * @param u Nó de partida
 */
void bellman_ford(vector<vii>& g,int u){

    cost.assign(g.size(),INF);
    // Inicializa o custo de u para ele mesmo
    cost[u] = 0;

    /***
     * Aplica o método de bellman ford: para cada aresta, aplique
     * a condição de relaxamento. Isso deve ser repetido |V| - 1 vezes,
     * pois um caminho possui no máximo |V|-1 arestas.
     ***/
    for(size_t k=0;k<g.size()-1;k++){
        for(size_t u=0;u<g.size;u++){
            for(auto& v: g[u]){
                cost[v.first] = min(cost[v.first],cost[u]+v.second);
            }
        }
    }

    /*** 
     * Realiza uma última verificação para checar se existem ciclos
     * negativos no grafo
     ***/
    bool has_negative_cycle = false;
    for(size_t u=0;u<g.size();u++){
        for(auto& v: g[u]){
            if(cost[u]+v.second < cost[v.first]){
                has_negative_cycle = true;
            }
        }
    }
}

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;

// Dividimos por 2 para evitar overflow na soma entre dois valores INF
const int INF = numeric_limits<int>::max()/2;

/**
 * @brief Dado um grafo representado por uma uma matrix de 
 * adjacências, calcule o menor caminho entre quaisquer par de vértices.
 * Ao término do algoritmo, a matriz de adjacências na posição g[u][v]
 * contém o custo do menor caminho entre u e v; 
 * 
 * @param g Grafo representado por uma matriz de adjacências
 */
void floyd_warshall(vector<vi>& g){

    /***
     * Caso base, o custo de cada nó para ele mesmo é zero e o custo
     * de todo nó u para todo nó v conectado por uma aresta (u,v) é o
     * peso da aresta (u,v). Caso contrário, o custo de u para v é infinito.
     ***/

    for(size_t i=0;i<g.size();i++){
        for(size_t j=0;j<g.size();j++){
            /***
             * Se não existe aresta de i para j, então a distância de
             * i para j é sinalizada como infinito
             ***/
            if(g[i][j]==-1){
                g[i][j] = INF;
            }
        }
        // Distância de um nó para ele mesmo é 0
        g[i][i] = 0;
    }

    /***
     * Calcula a menor distância entre todos os nós utilizando
     * os nós {0,1,2,...,k}
     ***/
    for(int k=0;k<g.size();k++){
        for(int i=0;i<g.size();i++){
            for(int j=0;j<g.size();j++){
                g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}