---
author: nguyencter
tags: Clique
title: Clique Solution
---

$\Huge\text{Clique Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/file/d/17jJcDZUqUnLEjdhnLWr7zTgxrTapW-Cu/view?usp=sharing)
📌 Tags: Backtrack
✍️ Writer: nguyencter
📋 Content:
[TOC]
:::

-----

## Giới Thiệu Đề Bài

**Clique**
Cho một đồ thị vô hướng G có n đỉnh m cạnh và số nguyên k.
**Yêu cầu**: Hãy tìm một clique có kích thước bằng k

-----

## Thuật toán
Đối với bài toán này ta sử dụng phương pháp quay lui để tìm k đỉnh tạo thành 1 clique.
Nhưng vì giới hạn $N$ lớn nên ta cần đặt cận để giảm độ phức tạp.

Ta sử dụng tập hợp $P$ để lưu lại các đỉnh tạo thành clique (ban đầu $P$ rỗng).

Recur(i,j) với mỗi đỉnh từ i+1 đến N ta kiểm tra xem nếu nó có cạnh nối trực tiếp tới mỗi phần tử trong $P$ hay không, nếu có thì thay đỉnh này thành phần tử thứ j của tập $P$ còn không thì xét đến đỉnh khác.

Tiếp tục cho đến khi số lượng phần tử của $P$ bằng với k thì in ra tập $P$.

----

Tham khảo code ở [đây](https://github.com/nguyencter/CODE/blob/main/clique.cpp)