MaxCutFree | Topcoder Archive

Problem Statement

You are given a simple undirected graph G on n nodes, numbered 0 through n-1. More precisely, you are given the int n and two equally-long int[]s a and b. For each valid index i, the graph contains an edge that connects the nodes a[i] and b[i].

An edge is called a bridge if the removal of this edge increases the number of connected components.

Given a subset S of nodes, the subgraph of G induced by S is a graph whose vertices are S and whose edges are all edges of G whose both endpoints are in S.

We are interested in sets S such that the subgraph induced by S does not contain any of the edges that are bridges in G. Compute and return the size of the largest such set.

Definition

Class:: MaxCutFree
Method:: solve
Parameters:: int, int[], int[]
Returns:: int
Method signature:: int solve(int n, int[] a, int[] b)
(be sure your method is public)

Notes

An isolated vertex does count as a connected component.

Constraints

n will be between 1 and 1,000, inclusive.
a will have between 0 and 1,500 elements, inclusive.
b will have the same number of elements as a.
Each element of a and b will be between 0 and n-1, inclusive.
The graph defined by the input will be a simple graph (without self-loops and duplicate edges).

Examples

```
4
```
```
{0, 1, 2, 0}
```
```
{1, 2, 0, 3}
```
```
Returns: 3
```
The edge 0-3 is a bridge. Thus, the set S cannot contain both node 0 and node 3. The largest two valid sets S are {0,1,2} and {1,2,3}.
```
6
```
```
{0,1,2,3,3}
```
```
{2,2,3,4,5}
```
```
Returns: 4
```
Each of these five edges is a bridge. The optimal solution is to take S = {0,1,4,5}.
```
7
```
```
{0,2,4}
```
```
{1,3,5}
```
```
Returns: 4
```
```
4
```
```
{0,0,0,1,1,2}
```
```
{1,2,3,2,3,3}
```
```
Returns: 4
```
This is a complete graph with no bridges. We can take its entire set of vertices as S.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.