Material complementar

GEMA

Como representar

Em C++, podemos representar uma lista de adjacências como um vector de vectors, ou um array de vectors:

int n, m; cin >> n >> m; // n=vertices, m=arestas
vector<vector<int>> edges(n); // edges[i] = {adjacentes a i}

for (int i = 0; i < m; i++) {
   int u, v; cin >> u >> v;
   edges[u].push_back(v); // u->v
   edges[v].push_back(u); // v->u (para grafos não direcionados)
}

// também poderia fazer um dos arrays estáticos:
const int MAXN = 1e5 + 5; // falando que o maximo de N é 10^5
vector<int> edges[MAXN];

DFS

Busca em profundidade. Implementação recursiva:

const int MAXN = 1e5 + 5;

vector<int> edges[MAXN];
bool vis[MAXN];

void dfs(int u) {
   vis[u] = true;
   for (int v : edges[u]) if (!vis[v]) {
      dfs(v);
   }
}

BFS

Busca em largura. Implementação com uma queue:

const int MAXN = 1e5 + 5;

vector<int> edges[MAXN];
int dist[MAXN];

void bfs(int s) { // vertice para iniciar a busca
   dist[s] = 1;
   queue<int> qu;
   qu.emplace(s);
   while(!qu.empty()) {
      int u = qu.front();
      qu.pop();
      for (int v : edges[u]) if (!dist[u]) {
         dist[v] = dist[u] + 1;
         qu.emplace(v);
      }
   }
}

Ordenação topológica

GEMA

Exemplo clássico: você tem um grafo em que os vértices são disciplinas e as arestas representam os pré-requisitos de determinadas matérias (u→v representa que u deve ser feito antes de v). Como pegar uma ordem possível de matérias para se formar?

const int MAXN = 1e5 + 5;

vector<int> edges[MAXN];
bool vis[MAXN];
vector<int> order;

void dfs(int u) {
   vis[u] = true;
   for (int v : edges[u]) if (!vis[v]) {
      dfs(v);
   }
   order.push_back(u);
}

// na main
for (int u = 1; u <= n; u++) if (!vis[u])
   dfs(u);

reverse(order.begin(), order.end());

Grafo bipartido

Exemplo: você quer formar dois times, mas existem algumas inimizades. Em um grafo que as pessoas são vértices e as arestas são inimizades (u→v representa que u e v são inimigas e não podem ficar no mesmo time), como pegar uma divisão possível?

Ideia básica: começa em um vértice qualquer de uma componente e fala que ele é do time 1. Depois, fala pra todos os vizinhos dele que eles agora são do time 2. E faz isso de forma recursiva. Se tiver algum ciclo de tamanho ímpar, é impossível.

const int MAXN = 1e5 + 5;

vector<int> edges[MAXN];
int color[MAXN]; // time[u] = 1 ou 2

void dfs(int u, int c) {
   color[u] = c;
   for (int v : edges[u]) {
      if (!color[v])
         dfs(v, 3 - c); // chama pro outro time
      else if (color[v] == color[u])
         cout << "IMPOSSIBLE!!!!";
   }
}

// na main
for (int u = 1; u <= n; u++) if (!color[u])
   dfs(u, 1);

Union-Find