레이팅 미적용설명
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\).
제약
입력 형식
- 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.
출력 형식
- Output the number of vertices in a maximum independent set of the input graph.
예제 1
입력
2 1
1 2
출력
1
예제 2
입력
4 5
1 2
2 3
3 4
4 1
1 3
출력
2
문제 정보