DWITE '07 R2 #5 - Bridges In A Graph

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE Online Computer Programming Contest, November 2007, Problem 5

A graph is a collection of nodes, called vertices, connected to each other in some fashion by edges. A graph is called connected if it is possible to find a path along edges from every point to every other point.

Below are two graphs:

One on the left is connected, while the one on the right is not connected (there is no path from node 1 to node 3).

An edge of a graph is called a bridge if by removing that edge the graph is no longer connected.

Edge 1-2 in the following graph is a bridge, since by removing it, the graph is no longer connected (no path from node 1 to any other node):

Edge 2-3 however, is not a bridge:

You are tasked with finding the number of edges, in a graph, that are bridges. You will be given 5 connected graphs, and you will output 5 single integers for the number of bridges found in graphs.

First line will contain a single integer N, number of vertices. Vertices will be numbered 1 to N. 1 \le N \le 100. Second line will contain a single integer M, number of edges. 0 \le M \le 1000. Followed by M lines, each describing an edge. An edge is described by two integers, separated by a space. All edges are valid. This format will be repeated 5 times (that is, a line after the last edge of the 1st graph, will be a single integer, describing a number of vertices in the 2nd graph).

The output will contain 5 lines, a single integer per line -- the number of bridges in the described graph.

Sample Input 1

6
7
1 2
1 3
1 4
1 5
3 5
6 2
6 1

Sample Output 1

1

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments


  • 0
    Swarley  commented on Oct. 14, 2018, 5:20 p.m. edited

    EDIT: Figured out the issue