📝 문제 정보#
문제#
무방향 단순 그래프 G = (V, E)에 대해, V’ ⊆ V인 부분집합 V’를 독립 집합(independent set)이라고 부르는 것은 V’의 어떤 두 원소도 간선으로 연결되어 있지 않을 때입니다. G의 독립 집합을 최대 독립 집합(maximum independent set)이라고 부르는 것은 G에 그보다 엄격하게 더 많은 정점을 가진 독립 집합이 없을 때입니다. 특정한 종류의 연결된 그래프 G가 주어졌을 때, G의 최대 독립 집합의 크기를 구하세요.
입력#
- 입력은 한 줄로 시작하며, 정수 n (1 ≤ n ≤ 100), 그래프의 정점 개수, 그리고 m (n − 1 ≤ m ≤ n + 15), 그래프의 간선 개수를 포함합니다.
- 그 다음 m개의 줄이 이어지며, 각 줄은 정수 a, b (1 ≤ a, b ≤ n)를 포함하여 정점 a와 b 사이에 간선이 있음을 나타냅니다.
이 입력으로 주어지는 그래프는 단순하고 연결되어 있음이 보장됩니다: 각 정점 쌍 사이에 최대 하나의 간선이 있고, 루프가 없으며, 각 정점 쌍 사이에 경로가 존재합니다.
출력#
- 입력 그래프의 최대 독립 집합에 포함된 정점의 개수를 출력합니다.
🧐 관찰 및 접근#
- 이분 그래프라면 쾨닉의 정리로 딸깍인데 ㅋㅋ
- 같은 느낌으로, 결국 최소 정점 커버를 구하는 것과 같다.
- 간선이 생각보다 적은게 힌트인가..?
- 그래프는 하나의 컴포넌트로 연결되어있고, 간선의 개수는 트리딱뎀 ~ 트리딱뎀 + 16이다.
- 트리에서 최대 독립집합은 어떻게 풀지?
- 이건 트리 DP로 되는거같다. 본인을 최대 독립집합에 포함시켰을때 / 포함시키지 않았을때의 맛으로.
- 간선이 트리 + 1개, 즉 $N$개 있다면?
- 트리랑 비슷하지만, 적어도 두개중에 하나는 안쓰는걸로 고정해야한다. (둘다 쓸순 없으니까)
- 그러면 양쪽을 고정해본상태로 각각 풀면, 두번 풀면 되겠는데?
- 간선이 트리 + 16개라면?
- 위와 같은 아이디어로 $2^{16}$번 하면 되지 않을까?
💻 풀이#
- 코드 (C++):
int N, M;
vector<int> links[101], childs[101];
vector<pii> backEdges;
bool visited[101];
void dfs(int c, int p){
visited[c] = true;
for(auto n: links[c]){
if(n == p) continue;
if(visited[n]){
if(c < n) backEdges.push_back({c, n});
}
else{
childs[c].push_back(n);
dfs(n, c);
}
}
}
bool prohibit[101];
int DP[101][2];
int dfs2(int c, bool used){
if(used && prohibit[c]) return -1e5;
if(DP[c][used] != -1) return DP[c][used];
int& ret = DP[c][used];
ret = 0;
for(auto n: childs[c]){
if(used) ret += dfs2(n, false);
else ret += max(dfs2(n, false), dfs2(n, true));
}
if(used) ret++;
return ret;
}
void solve(){
cin >> N >> M;
rep(i, 0, M){
int u, v; cin >> u >> v;
links[u].push_back(v);
links[v].push_back(u);
}
dfs(1, -1);
int sz = backEdges.size();
int ans = 0;
rep(i, 0, 1 << sz){
rep(j, 0, 101) prohibit[j] = false;
rep(j, 0, sz){
if(i & (1 << j)) prohibit[backEdges[j].first] = true;
else prohibit[backEdges[j].second] = true;
}
rep(j, 0, 101) rep(k, 0, 2) DP[j][k] = -1;
ans = max(ans, max(dfs2(1, false), dfs2(1, true)));
}
cout << ans;
}