Mostovi
레이팅 미적용의견: 0
When Leonhard Euler resolved the famous Königsberg bridge problem,
he had no clue he had discovered a whole new area of mathematics -
graph theory!
Unfortunately, the Königsberg bridge problem is far too easy for the
programmers of this era, so Euler came up with another probl\(em - th\)e
Zagreb bridge problem!
The bridges of Zagreb form a graph with \(n\) nodes and \(m\) edges where the edges represent the bridges and
the nodes represent the riverine islands. The graph is connected, in other words, it’s possible to get from
any node to any other by traveling across the edges. Now Euler asked, how many edges are there such
that after their removal the graph becomes disconnected?
Again, Euler didn’t know that this problem is also famous today (those damn Codeforces blogs). So the
author of this problem decided to give you an even harder one, how many edges are there such that after
the removal of the nodes which it connects, the remaining \(n - 2\) nodes become disconnected?
Subtask 1 (13 points): \(n \le 100\), \(m \le 300\)
Subtask 2 (17 points): \(n \le 1\,000\), \(m \le 3\,000\)
Subtask 3 (25 points): \(n \le 1\,000\)
Subtask 4 (12 points): \(m - n \le 20\)
Subtask 5 (43 points): No additional constraints.
The first line contains integers \(n\) and \(m\) (\(4 \le n \le 100\,000\), \(n - 1 \le m \le 300\,000\)) - the number of nodes
and edges respectively.
Each of the next \(m\) lines contains integers \(a@@RISE_MATH_BLOCK_0@@i\) (\(1 \le a@@RISE_MATH_BLOCK_1@@i\) and \(b\)\(i\) are
connected with an edge.
There are no loops or multiple edges.
In a single line output the number of edges with the given property.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 13점 | \(n \le 100\), \(m \le 300\) |
2 | 17점 | \(n \le 1\,000\), \(m \le 3\,000\) |
3 | 25점 | \(n \le 1\,000\) |
4 | 12점 | \(m - n \le 20\) |
5 | 43점 | No additional constraints. |
4 5
1 2
2 3
3 4
4 1
1 316 7
1 2
2 4
2 6
3 5
6 1
4 3
2 54Clarification of the first example:
By removing edge (1, 3) and corresponding nodes 1 and 1, the remaining graph has two connected
components, node 2 and node 4. In other words, it is not connected. It is easy to check it is the only edge
with this property.
Clarification of the second example:
The edges with the given property are (1, 2), (2, 4), (2, 6) abd (2, 5).
평가 및 의견
Mostovi
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Mostovi