Maximum clique - MarisaOJ: Marisa Online Judge

Maximum clique

Time limit: 2000 ms
Memory limit: 256 MB
Given an undirected graph pf $n$ vertices and $m$ edges, the goal is to find the largest clique (a complete subgraph where every pair of vertices is connected) within the graph. ### Input - First line contains two integers $n$ and $m$. - The next $m$ lines, each line contains two integers $u,v$, there is an edge between $u$ and $v$. ### Output - The first line contains an integer $k$, the size of the clique. - The second line contains $k$ integers, denoting vertices of the clique. ### Constraints - $1 \le n \le 200$ - $1 \le m \le \frac{n(n-1)}{2}$. - $1 \le u, v \le n$. ### Example Input: ``` 4 5 1 2 2 3 1 3 4 3 1 4 ``` Output: ``` 3 1 2 3 ``` ### Scoring - All test cases are scored equally. - Consider the jury's answer as $Y$ and your answer as $X$. - If $X \ge Y$, you receive a score of $100\\%$ for test case. - If $1 < \frac{Y}{X} \le 1.5$, your score for the test case is calculated as $(\frac{3X - 2Y}{X})^3\times 100 \\%$. - If $\frac{Y}{X} > 1.5$, you receive a score of $0\\%$ for the test case.