Forest

Go to the Jutge statement of the problem

A forest is a graph without cycles, and each of its connected components is a tree. Given an undirected graph, is it a forest? In case it is, how many trees does it have?

Input: Input consists of several graphs. Every graph starts with its number of vertices n and its number of edges m, followed by m pairs x y indicating an edge between vertices x and y. Assume 1 \leq n \leq 10^4, 0 \leq m < n, that vertices are numbered from 0 to n−1, and that there are neither repeated edges nor edges of the type x x.

Output: For every graph, if it is a forest print the number of trees it has. Otherwise, print no.

Hint

This problem is related to Problem 5.23 you will see in Problem Class P6.

A possible C++ code to start the problem

// Forest
#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& father){
  // 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;
    }
}

A possible solution

// Forest
#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& father){
    if (visited[v]) return true;
    visited[v] = true;
    for (int u : g[v]){
        if (father[v] != u){
            father[u] = v;
            if (cyclic(g, u, visited, father)) return true;
        }
    }
    return false;
}

int count_trees(const VVI& g){
    int n = g.size();
    int n_trees = 0;
    VB visited(n, false);
    VI father(n, -1);
    for (int v = 0; v < n; ++v){
        if (not visited[v]){
            if (cyclic(g, v, visited,father)) 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;
    }
}