report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
  • Problem
  • Submit
  • Results
Maximum clique - FlandreOJ: Flandre 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.
Introduction to Heuristic
Apple
Travelling Salesman Problem 3
Custom keyboard 2
Maximum clique
Superstring 2
Knapsack 5
Min-Max mTSP
Topic
Heuristic
Rating 2000
Solution (0) Solution