Hola, estoy resolviendo el problema “¿Es un árbol?” del Nivel 2 de la Nacional de 2012.
Mi idea se basa en la siguiente secuencia de pasos:
1- Hacer un conteo de cuántos arcos llegan a cada nodo.
2- “Anotar” a qué nodos no llega ningún arco.
3- “Anotar” a qué nodos llega más de un arco.
4- Con la información que ya tengo, determino si se cumplen las reglas 1 y 2.
5- Para determinar la regla 3, doy por asumido de forma inicial que si la regla 1 no se cumple, esta si se cumple, ya que si la regla 3 se cumple o no se cumple la regla 1 (no se si interpreté bien esta parte), hay que mostrar un cero si el grafo planteado no es un árbol.
6- Si la regla 3 no se cumple inicialmente (es decir si se cumple la regla 1), hago un BFS desde la raíz y tomo distancias dejar en claro a qué nodos se logró llegar. También podría haber tomado true o false si logré llegar a cierto nodo ya que es exactamente lo mismo.
7- Chequeo que a todos los nodos se les haya asignado una distancia. Caso contrario, los anoto como inalcanzables y anoto que no se cumple la regla 3.
8- Finalmente, muestro el resultado.
Dejo acá abajo mi código. Desde ya muchas gracias por leer, y si me pueden ayudar con mi solución voy a estar más que agradecido.
Código
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < n; i++)
#define debug(x) cout << #x << " = " << x << endl
int main(){
ifstream cin("arbol.in");
ofstream cout("arbol.out");
int N, M;
cin >> N >> M;
vector<vector<int>> grafo(N+1);
forn(i, M){
int u, v;
cin >> u >> v;
grafo[u].push_back(v);
}
vector<int> arcosLlegan(N+1, 0);
for(int i = 1; i <= N; i++){
for(int j = 0; j < grafo[i].size(); j++){
arcosLlegan[grafo[i][j]]++;
}
}
vector<int> posiblesRaices;
vector<int> llegaMasDeUno;
for(int i = 1; i <= N; i++){
if(arcosLlegan[i] == 0){
posiblesRaices.push_back(i);
}else if(arcosLlegan[i] > 1){
llegaMasDeUno.push_back(i);
}
}
bool regla1 = posiblesRaices.size() == 1;
bool regla2 = llegaMasDeUno.size() == 0;
bool regla3 = !regla1;
vector<int> inllegables;
if(!regla3){
int source = posiblesRaices[0];
vector<int> dist(N+1, -1);
vector<bool> marked(N+1, false);
queue<int> q;
q.push(source);
dist[source] = 0;
marked[source] = true;
while(!q.empty()){
int n = q.front();
q.pop();
for(int i = 0; i < grafo[n].size(); i++){
int vecino = grafo[n][i];
if(!marked[vecino]){
marked[vecino] = true;
dist[vecino] = dist[n] + 1;
q.push(vecino);
}
}
}
for(int i = 1; i <= N; i++){
if(dist[i] == -1){
inllegables.push_back(i);
}
}
regla3 = inllegables.size() == 0;
}
if(regla1 and regla2 and regla3){
cout << "Si" << endl;
}else{
cout << "No" << endl;
if(posiblesRaices.size() == 0) cout << 0;
else{
for(int i = 0; i < posiblesRaices.size(); i++){
cout << posiblesRaices[i] << " ";
}
}
cout << endl;
if(regla2) cout << 0;
else{
for(int i = 0; i < llegaMasDeUno.size(); i++){
cout << llegaMasDeUno[i] << " ";
}
}
cout << endl;
if(regla3) cout << 0;
else{
for(int i = 0; i < inllegables.size(); i++){
cout << inllegables[i] << " ";
}
}
cout << endl;
}
}