In this HackerEarth Easylife problem solution Given an undirected graph. Density of a graph is |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".


HackerEarth Easylife problem solution


HackerEarth Easylife problem solution.

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.io.Writer;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
FastScanner in = new FastScanner(inputStream);
FastPrinter out = new FastPrinter(outputStream);
EasyLife solver = new EasyLife();
solver.solve(1, in, out);
out.close();
}

static class EasyLife {
public void solve(int testNumber, FastScanner in, FastPrinter out) {
int n = in.nextInt();
int m = in.nextInt();
int[] from = new int[m];
int[] to = new int[m];
for (int i = 0; i < m; i++) {
from[i] = in.nextInt() - 1;
to[i] = in.nextInt() - 1;
}
DisjointSetUnion dsu = new DisjointSetUnion(n);
for (int i = 0; i < m; i++) {
dsu.union(from[i], to[i]);
}
int[] vertices = new int[n];
int[] edges = new int[n];
for (int i = 0; i < n; i++) {
vertices[dsu.get(i)]++;
}
for (int i = 0; i < m; i++) {
edges[dsu.get(from[i])]++;
}
boolean canOne = false;
int maxLess = 0;
for (int i = 0; i < n; i++) {
if (i != dsu.get(i)) continue;
if (vertices[i] < edges[i]) {
out.println(">1");
return;
}
if (vertices[i] == edges[i]) {
canOne = true;
} else {
maxLess = Math.max(maxLess, vertices[i]);
}
}
if (canOne) {
out.println("1/1");
} else {
out.println((maxLess - 1) + "/" + maxLess);
}
}

}

static class FastPrinter extends PrintWriter {
public FastPrinter(OutputStream out) {
super(out);
}

public FastPrinter(Writer out) {
super(out);
}

}

static class DisjointSetUnion {
int[] p;

public DisjointSetUnion(int n) {
p = new int[n];
clear();
}

public void clear() {
for (int i = 0; i < p.length; i++) {
p[i] = i;
}
}

public int get(int x) {
int y = x;
while (y != p[y]) {
y = p[y];
}
while (x != p[x]) {
int t = p[x];
p[x] = y;
x = t;
}
return y;
}

public boolean union(int a, int b) {
a = get(a);
b = get(b);
p[a] = b;
return a != b;
}

}

static class FastScanner extends BufferedReader {
public FastScanner(InputStream is) {
super(new InputStreamReader(is));
}


public int read() {
try {
int ret = super.read();
return ret;
} catch (IOException e) {
throw new InputMismatchException();
}
}

static boolean isWhiteSpace(int c) {
return c >= 0 && c <= 32;
}

public int nextInt() {
int c = read();
while (isWhiteSpace(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int ret = 0;
while (c >= 0 && !isWhiteSpace(c)) {
if (c < '0' || c > '9') {
throw new NumberFormatException("digit expected " + (char) c
+ " found");
}
ret = ret * 10 + c - '0';
c = read();
}
return ret * sgn;
}

public String readLine() {
try {
return super.readLine();
} catch (IOException e) {
return null;
}
}

}
}