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];
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);
}
}
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);
}
}
}
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());
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);