BAPC19-038.Inquiry II

Medium · 1 s · 256 MB

icpc
bapc
2019

For an undirected, simple graph $G = (V, E)$ we call a subset $V' \subseteq V$ an independent set if no two elements of $V'$ are connected by an edge. An independent set of $G$ is called a maximum independent set if there is no independent set in $G$ with strictly more vertices. Given a specific kind of connected graph $G$ , find the size of a maximum independent set of $G$ .

Giriş formatı

• The input starts with one line, containing integers $n$ ( $1 \leq n \leq 100$ ), the number of vertices in the graph, and $m$ ( $n-1 \leq m \leq n + 15$ ), the number of edges in the graph.

• Then follow $m$ lines, each containing integers $a, b$ ( $1 \leq a, b \leq n$ ) indicating that there is an edge between vertices $a$ and $b$ .

The graph given by this input is guaranteed to be both simple and connected: there is at most one edge between each pair of vertices, there are no loops, and there is a path between each pair of vertices.

Çıxış formatı

• Output the number of vertices in a maximum independent set of the input graph.

Qeyd

Source: Benelux Algorithm Programming Contest 2019 · Author: Timon Knigge · License: CC BY-SA 4.0 · Original: https://bapc.eu · Statement adapted for AlgoLens and shared under the same license.

Nümunələr

Giriş #1

2 1
1 2

Çıxış #1

Giriş #2

Çıxış #2

Giriş formatı

• The input starts with one line, containing integers $n$ ( $1 \leq n \leq 100$ ), the number of vertices in the graph, and $m$ ( $n-1 \leq m \leq n + 15$ ), the number of edges in the graph.

• Then follow $m$ lines, each containing integers $a, b$ ( $1 \leq a, b \leq n$ ) indicating that there is an edge between vertices $a$ and $b$ .