978. Get a tree

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.

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.

Sample input	Sample output
4 4 1 2 2 3 3 4 4 1	1 2 2 3 3 4

SOLUTION

graphs – depth first search

Algorithm analysis

Run the depth first search from the first vertex. Build the search tree and print all its edges.

Example

Graph given in the input, has the form:

Depth first serch from vertex 1 will pass through the edges: (1, 2), (2, 3), (3, 4).

Algorithm realization

The adjacency matrix is stored in array g.

#define MAX 101

int g[MAX][MAX], used[MAX];

Function dfs implements the depth first search from vertex v. Print each edge (v, i) of the tree during the search.

void dfs(int v)

{

int i;

used[v] = 1;

for(i = 1; i <= n; i++)

if (g[v][i] && !used[i])

{

printf("%d %d\n",v,i);

dfs(i);

}

}

The main part of the program. Read the input data.

scanf("%d %d",&n,&m);

memset(g,0,sizeof(g)); memset(used,0,sizeof(used));

while(m--)

{

scanf("%d %d",&a,&b);

g[a][b] = g[b][a] = 1;

}

Run the depth first search from the first vertex.

dfs(1);

Java realization

import java.util.*;

public class Main

{

static int g[][], used[];

static int n, m;

static void dfs(int v)

{

used[v] = 1;

for(int i = 1; i <= n; i++)

if (g[v][i] == 1 && used[i] == 0)

{

System.out.println(v + " " + i);

dfs(i);

}

used[v] = 2;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

n = con.nextInt();

m = con.nextInt();

g = new int[n+1][n+1];

used = new int[n+1];

for(int i = 0; i < m; i++)

{

int a = con.nextInt();

int b = con.nextInt();

g[a][b] = g[b][a] = 1;

}

dfs(1);

con.close();

}

}