L3: Graph algorithms I

Posible flujo de trabajo

  • descargar el archivo .zip zip de el problema de el Jutge.org Jutge.org que se quiere resolver
  • unzip el archivo
  • en la carpeta obtenida teneis:
    • un file .pdf con el enunciado del problema,
    • uno o más files de texto con ejemplos de input sample.inp
    • los correspondiente outputs correctos sample.cor
  • crear un file con el vuestro codigo sorgente C++ para resolver el problema
  • compilar el codigo sorgente con g++ -std=c++11.
    Posibles flags utiles: -Wall -Wextra -Wno-overflow -Wpedantic -Werror -D_GLIBCXX_DEBUG
  • testar el ejecutable en los ejemplos:
    por ejemplo con ./a.out < sample.inp > output
  • testar que el file de output sea correcto:
    por ejemplo con diff output sample.cor
  • una vez que estais convencidos que vuestra solucion es correcta, enviarla al Jutge
    • no enviar al Jutge soluciones que no sean correctas en los ejemplos que teneis!
    • no intentar re-escribir a mano los ejemplos de input

Problemas sobre Graph Algorithms

Los problemas de el apartado EDA Curs 2023/2024 Q2 \(\rightarrow\) Graph algorithms.

Depth-First Search
P70690 Treasures in a map (1)
P90766 Treasures in a map (3)
X41530 Forest (~ Problem 5.23 you will see in Problem Class P6)
P29033 Two colors
P53547 Tiny bishops
P40479 Painting a board

Topological Sort
P14952 Topological sort (~ Problem 5.12 you will see in Problem class P6)
P16249 Task ordering
X21319 Circuit Value Problem :exclamation::exclamation:

Breadth-First Search
P60796 Treasures in a map (2)
P39846 Treasures in a map (4)
P88760 Zamburguesas :exclamation:

:exclamation: = the problem might be harder than the rest

Problemas resueltos en clase

P70690 Treasures in a map (1)

Possible C++ code to start problem P70690 (recursive) 
//Treasures in a map (1)
// can we reach a treasure? 
#include<iostream>
#include<vector>

using namespace std;

using VVC =  vector<vector<char>>;
using VVB = vector<vector<bool>>;

struct Pos {
    int i, j;
    Pos (int ii = 0, int jj = 0) : i(ii), j(jj) {}
};


const int N_DIRS = 4;
const Pos DIRS[N_DIRS] = { {1,0}, {-1,0}, {0,1}, {0,-1} };

bool within_range(Pos p, int n, int m){
    return 0<=p.i and p.i < n and 0 <=p.j and p.j < m;
}


bool dfs(const VVC& map, VVB& visited, Pos p){
  // do it recursively
}

int main (){
    int n, m;
    cin >> n >> m;
    VVC map(n, vector<char>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> map[i][j];
    Pos p;
    cin >> p.i >> p.j;

    VVB visited(n, vector<bool>(m, false));
    cout << (dfs(map, visited, Pos(p.i-1, p.j-1)) ? "yes" : "no") << endl; 
}
Possible C++ code to start problem P70690 (iterative) 
//Treasures in a map (1)
// can we reach a treasure? 
#include<iostream>
#include<vector>
//#include<stack> or #include<queue>?

using namespace std;

using VVC =  vector<vector<char>>;
using VVB = vector<vector<bool>>;
using Pos = pair<int,int>;

const int N_DIRS = 4;
const pair<int,int> DIRS[N_DIRS] = { {1,0}, {-1,0}, {0,1}, {0,-1} };

bool within_range(int i, int j, int n, int m){
    return 0<=i and i < n and 0 <=j and j < m;
}


bool dfs(const VVC& map, int i0, int j0){
    // do it iteratively
    // stack or queue?
}

int main (){
    int n, m;
    cin >> n >> m;
    VVC map(n, vector<char>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> map[i][j];
    int r,c;
    cin >> r >> c;

    cout << (dfs(map, r-1, c-1) ? "yes" : "no") << endl; 
}
Possible solution (recursive) 
//Treasures in a map (1)
// can we reach a treasure? 
#include<iostream>
#include<vector>

using namespace std;

using VVC =  vector<vector<char>>;
using VVB = vector<vector<bool>>;

struct Pos {
    int i, j;
    Pos (int ii = 0, int jj = 0) : i(ii), j(jj) {}
};


const int N_DIRS = 4;
const Pos DIRS[N_DIRS] = { {1,0}, {-1,0}, {0,1}, {0,-1} };

bool within_range(Pos p, int n, int m){
    return 0<=p.i and p.i < n and 0 <=p.j and p.j < m;
}


bool dfs(const VVC& map, VVB& visited, Pos p){
    int n = map.size();
    int m = map[0].size();
    visited[p.i][p.j] = true;
    if (map[p.i][p.j] == 't') return true;
    for (int k = 0 ; k < N_DIRS; ++k){
        Pos q(p.i+DIRS[k].i, p.j + DIRS[k].j);
        if (within_range(q, n, m) and !visited[q.i][q.j] and map[q.i][q.j] != 'X') 
            if(dfs(map, visited, q)) return true;
    }
    return false;
}

int main (){
    int n, m;
    cin >> n >> m;
    VVC map(n, vector<char>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> map[i][j];
    Pos p;
    cin >> p.i >> p.j;

    VVB visited(n, vector<bool>(m, false));
    cout << (dfs(map, visited, Pos(p.i-1, p.j-1)) ? "yes" : "no") << endl; 
}
Possible solution (iterative) 
//Treasures in a map (1)
// can we reach a treasure? 
#include<iostream>
#include<vector>
#include<stack>

using namespace std;

using VVC =  vector<vector<char>>;
using VVB = vector<vector<bool>>;
using Pos = pair<int,int>;

const int N_DIRS = 4;
const pair<int,int> DIRS[N_DIRS] = { {1,0}, {-1,0}, {0,1}, {0,-1} };

bool within_range(int i, int j, int n, int m){
    return 0<=i and i < n and 0 <=j and j < m;
}


bool dfs(const VVC& map, int i0, int j0){
    int n = map.size();
    int m = map[0].size();
    VVB visited(n, vector<bool>(m, false));
    stack<Pos> s;
    s.push({i0,j0});
    while(not s.empty()){
        Pos p = s.top();
        s.pop();
        int i = p.first;
        int j = p.second;
        if (not visited[i][j]){
            visited[i][j] = true;
            if (map[i][j] == 't') return true;
            for (int k = 0; k < N_DIRS; ++k){
                int ii = i + DIRS[k].first;
                int jj = j + DIRS[k].second;
                if(within_range(ii, jj, n, m) and map[ii][jj]!='X'){
                s.push({ii,jj});
                }
            }
        }
    }
    return false;
}

int main (){
    int n, m;
    cin >> n >> m;
    VVC map(n, vector<char>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> map[i][j];
    int r,c;
    cin >> r >> c;

    cout << (dfs(map, r-1, c-1) ? "yes" : "no") << endl; 
}


P60796 Treasures in a map (2)

Possible C++ code to start problem P60796 
#include<iostream>
#include<vector>
#include<queue>

using namespace std;
using VVC = vector<vector<char>>; 
using VVI = vector<vector<int>>;
using VI = vector<int>;
using P = pair<int,int>;

const int N_DIRS = 4;
const int UNDEF = -1;
const pair<int,int> DIRS[N_DIRS] = { {1,0}, {-1,0}, {0,1}, {0,-1} };

bool within_range(int i, int j, int n, int m){
    return 0<=i and i < n and 0 <=j and j < m;
}

int bfs(const VVC& map, int i0, int j0){
    // similar as the dfs interative but use a queue
    // and update the distance accordingly
}

int main(){
    int n, m;
    cin >> n >> m;
    VVC map(n, vector<char>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> map[i][j];
    int r,c;
    cin >> r >> c;
    int dist = bfs(map, r-1, c-1);
    if (dist == UNDEF) cout << "no treasure can be reached" << endl;
    else cout << "minimum distance: " << dist << endl;
}
Possible solution 
#include<iostream>
#include<vector>
#include<queue>

using namespace std;
using VVC = vector<vector<char>>; 
using VVI = vector<vector<int>>;
using VI = vector<int>;
using P = pair<int,int>;

const int N_DIRS = 4;
const int UNDEF = -1;
const pair<int,int> DIRS[N_DIRS] = { {1,0}, {-1,0}, {0,1}, {0,-1} };

bool within_range(int i, int j, int n, int m){
    return 0<=i and i < n and 0 <=j and j < m;
}

int bfs(const VVC& map, int i0, int j0){
    // similar as a dfs iterative but use a queue
    // and update the distance accordingly 
    int n = map.size();
    int m = map[0].size();
    queue<P> q;
    VVI dist(n, VI(m, UNDEF));
    q.push({i0,j0});
    dist[i0][j0] = 0;
    while(not q.empty()){
        P p = q.front();
        q.pop();
        int i = p.first;
        int j = p.second;
        if (map[i][j] == 't') return dist[i][j];
            for (int k = 0; k < N_DIRS; ++k){
                int ii = i + DIRS[k].first;
                int jj = j + DIRS[k].second;
                if(within_range(ii, jj, n, m) and map[ii][jj]!='X' and dist[ii][jj]==UNDEF){
                    q.push({ii,jj});
                    dist[ii][jj] = 1 + dist[i][j];
                }
            }
    }
    return UNDEF;
}

int main(){
    int n, m;
    cin >> n >> m;
    VVC map(n, vector<char>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> map[i][j];
    int r,c;
    cin >> r >> c;
    int dist = bfs(map, r-1, c-1);
    if (dist == UNDEF) cout << "no treasure can be reached" << endl;
    else cout << "minimum distance: " << dist << endl;
}


X41530 Forest

Possible C++ code to start problem X41530 
#include<iostream>
#include<vector>

using namespace std;
using VVI = vector<vector<int>>;
using VB = vector<bool>;
using VI = vector<int>;

bool cyclic(const VVI& g, int v, VB& visited, VI& parent){
  // similar dfs
  // returns true iff the connected component containing v contains a cycle

}

int count_trees(const VVI& g){
    // use the auxiliary function cyclic to count the number of trees

}

int main(){
    int n, m;
    while (cin >> n >> m){
        VVI g(n);
        for (int k = 0; k < m; ++k){
            int u,v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int n_trees = count_trees(g); // -1 if g is not a tree
        if (n_trees == -1 ) cout << "no" << endl;
        else                cout << n_trees << endl;
    }
}
Possible solution 
#include<iostream>
#include<vector>

using namespace std;
using VVI = vector<vector<int>>;
using VB = vector<bool>;
using VI = vector<int>;

bool cyclic(const VVI& g, int v, VB& visited, VI& parent){
    if (visited[v]) return true;
    visited[v] = true;
    for (int u : g[v]){
        if (parent[v] != u){
            parent[u] = v;
            if (cyclic(g, u, visited, parent)) return true;
        }
    }
    return false;
}

int count_trees(const VVI& g){
    int n = g.size();
    int n_trees = 0;
    VB visited(n, false);
    VI parent(n, -1);
    for (int v = 0; v < n; ++v){
        if (not visited[v]){
            if (cyclic(g, v, visited,parent)) return -1;
            else ++n_trees;
        }
    }
    return n_trees;
}

int main(){
    int n, m;
    while (cin >> n >> m){
        VVI g(n);
        for (int k = 0; k < m; ++k){
            int u,v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int n_trees = count_trees(g); // -1 if g is not a tree
        if (n_trees == -1 ) cout << "no" << endl;
        else                cout << n_trees << endl;
    }
}


P14952 Topological sort

Possible C++ code to start problem P14952 
#include<iostream>
#include<vector>
#include<queue>

using namespace std;
using graph = vector<vector<int>>;
using VI = vector<int>;

VI compute_ordering(const graph& g, VI& indegree){
   // suggestion: use a priority_queue
}

void write(const VI& v){
    cout << v[0];
    for (int i = 1; i < v.size(); ++i)
        cout  << ' ' << v[i];
    cout << endl;
}

int main(){
    int n, m;
    while(cin >> n >> m){
        graph g(n);
        VI indegree(n, 0);
        for (int i = 0; i < m; ++i){
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            ++indegree[v];
        }
    VI ord = compute_ordering(g,indegree);
    write(ord);
    }
}
Possible solution 
#include<iostream>
#include<vector>
#include<queue>

using namespace std;
using graph = vector<vector<int>>;
using VI = vector<int>;

VI compute_ordering(const graph& g, VI& indegree){
    int n = g.size();
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int u =0; u < n; ++u){
        if (indegree[u]==0) pq.push(u);
    }
    VI ord;
    while(not pq.empty()){
        int u = pq.top();
        pq.pop();
        ord.push_back(u);
        for (int k = 0; k < g[u].size(); ++k){
            int v = g[u][k];
            --indegree[v];
            if (indegree[v]==0) pq.push(v);
        }
    }
    return ord;
}

void write(const VI& v){
    cout << v[0];
    for (int i = 1; i < v.size(); ++i)
        cout  << ' ' << v[i];
    cout << endl;
}

int main(){
    int n, m;
    while(cin >> n >> m){
        graph g(n);
        VI indegree(n, 0);
        for (int i = 0; i < m; ++i){
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            ++indegree[v];
        }
    VI ord = compute_ordering(g,indegree);
    write(ord);
    }
}