All Tracks Algorithms Graphs Depth First Search Problem

Easylife
Tag(s):

Algorithms, DFS, Easy

Problem
Editorial
Analytics

Given an undirected graph. Density of a graph is $$\frac{|E|}{|V|}$$. Your task is to choose non-empty set of vertices $$V$$ such that subgraph induced on $$V$$ has maximal density and print this density. But if maximal density is strictly greater than $$1$$, just print ">1".

Input format

The first line of input contains two integers $$n$$ and $$m$$ - number of edges and vertices in the graph, respectively ($$1 \le n \le 10^{5}$$, $$0 \le m \le 2 \cdot 10^{5}$$).

Then $$m$$ lines with edge descriptions follows. Each line contains two integers $$u$$, $$v$$ - vertices incident to this edge ($$1 \le u, v \le n$$, $$u \ne v$$).

Output format

If maximal density of a subgraph is not bigger than $$1$$, then print it as irreducible fraction. Otherwise, print ">1" (without quotes).

Scoring

$$n \le 17$$, $$m \le 50$$ - 15 points.

$$n \le 17$$, $$m \le 2 \cdot 10^{5}$$ - 10 points.

$$n \le 70$$, $$m \le 200$$ - 20 points.

$$n \le 70$$, $$m \le 2 \cdot 10^{5}$$ - 5 points.

$$n \le 10^{5}$$, $$m \le 2 \cdot 10^{5}$$ - 50 points.

SAMPLE INPUT
5 3
1 4
2 3
5 2
SAMPLE OUTPUT
2/3
Explanation

The best option is to choose vertices 2, 3 and 5.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

October Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications