Graphs

[leo24]

The connected undirected graph without loops and multiple edges is given. You are
allowed to remove the edges from it. Obtain a tree from the graph.

Specifications

Input

The first line contains the number of vertices n (1 ≤ n ≤ 100) and the number of edges m of the
graph. The next m pairs of numbers define the edges. It is guaranteed that the graph is connected.

Output

Print n - 1 pairs of numbers - the edges that will be included in a tree. The edges can be displayed
in any order.

Example input

4 4
1 2
2 3
3 4
4 1

Example output

1 2
2 3
3 4

[Cubbi]

You could use any spanning tree algorithm, for example, Kruslal:

#include <vector>
#include <iterator>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>

int main()
{
    using namespace boost;
    typedef adjacency_list<vecS, vecS, undirectedS, no_property,
                           property<edge_weight_t, int> > graph_t;

    int v, e;
    std::cin >> v >> e;

    graph_t g(e);

    // load the data into the graph
    while(e-->0) {
        int from, to;
        std::cin >> from >> to;
        add_edge(from, to, g);
    }

    typedef graph_traits<graph_t>::edge_descriptor edge_t;
    std::vector<edge_t> mst;
    kruskal_minimum_spanning_tree(g, std::back_inserter(mst));
    for(const auto& edge : mst)
        std::cout << source(edge, g) << ' ' << target(edge,g) << '\n';
}

live demo: http://coliru.stacked-crooked.com/a/cf98bc775f7ac9e3