Boj 2051) 최소 버텍스 커버

문제

백준 2051

설명

Wiki 를 참고해 Vertex Cover 를 구성해냈다.

시간 복잡도

O(\(VE\))

• \(N\), \(M\) 을 기준으로 하면 O(\((N+M)(NM)\))
• 간선이 의외로 몇개 없는듯.

코드

const int MAX_IN = 1001;
vector<int> lines[MAX_IN];
bool V[MAX_IN], A[MAX_IN]; int B[MAX_IN];

bool DFS(int cur)
{
	if (V[cur]) return false;          // DFS 에서 visit 확인. 
	V[cur] = true;

	for (int l : lines[cur])
	{
		if (B[l] == 0 || DFS(B[l]))  // exposed vertex 가 나올때까지 dfs
		{
			B[l] = cur;
			A[cur] = true;
			return true;
		}
	}
	return false;
}

bool ZL[MAX_IN], ZR[MAX_IN]; int nZL, nZR;
void DFSZ(int in)
{
	if (ZL[in]) return;
	ZL[in] = true;
	nZL++;
	
	for (int l : lines[in])
		if(B[l] && !ZR[l])
		{
			ZR[l] = true;
			nZR++;
			DFSZ(B[l]);
		}
}

int main()
{
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		int num; cin >> num;
		while (num--)
		{
			int b; cin >> b;
			lines[i].push_back(b);
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		fill(V, V + n + 1, 0);
		if (DFS(i)) ans++;
	}

	cout << ans << endl;

	// Z 찾기
	for (int i = 1; i <= n; i++) if (!A[i]) DFSZ(i);

	// A 에서 Z 여집합 구하기
	cout << n - nZL << ' ';
	for (int i = 1; i <= n; i++) if (!ZL[i]) cout << i << ' ';
	
	// B 에서 Z 교집합 구하기
	cout << endl << nZR << ' ';
	for (int i = 1; i <= n; i++) if (ZR[i]) cout << i << ' ';
}