Densest subgraph

input/code.cpp: In function 'bool flow_ok(ld)':
input/code.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < cp.size()-1; ++i) {
                    ~~^~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 100;
const int S = 0;
const int T = N+1;

int n, m;
vector<int> g[N+5];
ll d[N+5][N+5];
int v[N+5];
int gvis = 0;

vector<int> cp;

bool rvis[N+5];
vector<int> res;

void set_weights(ld gp) {
	const ll MP = 1000000000;
	ll ig = (ll)(gp*MP);

	for (int a : g[S]) {
		d[S][a] = m*MP;
		d[a][S] = 0;
	}
	for (int a : g[T]) {
		d[a][T] = m*MP + 2*ig - (g[a].size()-2)*MP;
		d[T][a] = 0;
	}
	for (int i = 1; i <= n; ++i) {
		for (int a : g[i]) {
			if (a == S || a == T) continue;
			d[i][a] = 1*MP;
		}
	}
}

ll dfs(int s, int t, ll th, int cvis, ll cmin) {
	if (v[s] == cvis) return -1;
	v[s] = cvis;
	cp.push_back(s);
	if (s == t) return cmin;

	for (int a : g[s]) {
		if (d[s][a] < th) continue;
		ll cres = dfs(a, t, th, cvis, min(cmin, d[s][a]));
		if (cres != -1) return cres;
	}
	cp.pop_back();
	return -1;
}

void get_res(int s) {
	if (rvis[s]) return;
	rvis[s] = true;
	if (!(s == S || s == T)) {
		res.push_back(s);
	}
	for (int a : g[s]) {
		if (d[s][a] == 0) continue;
		get_res(a);
	}
}

bool flow_ok(ld gp) {
	set_weights(gp);

	ll cth = (1LL<<60);
	while (true) {
		gvis++;
		cp.clear();
		ll minw = dfs(S, T, cth, gvis, 1000000000000000005);
		if (minw != -1) {
			for (int i = 0; i < cp.size()-1; ++i) {
				int fn = cp[i];
				int sn = cp[i+1];
				d[fn][sn] -= minw;
				d[sn][fn] += minw;
			}
		}
		else {
			if (cth == 1) break;
			cth /= 2;
		}
	}

	for (int a : g[S]) {
		if (d[S][a] > 0) {
			return true;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 1; i <= n; ++i) {
		g[S].push_back(i);
		g[i].push_back(S);
		g[i].push_back(T);
		g[T].push_back(i);
	}

	ld gp = 0;
	ld jp = (1LL<<30);
	for (int i = 0; i < 100; ++i) {
		if (flow_ok(gp+jp)) gp += jp;
		jp /= 2;
	}
	flow_ok(gp); // build densest subgraph
	get_res(S); // find densest subgraph

	int rn = 0, rm = 0;
	for (int i = 1; i <= n; ++i) {
		if (rvis[i]) {
			rn++;
			for (int a : g[i]) {
				if (!rvis[a] || a == S || a == T) continue;
				rm++;
			}
		}
	}
	rm /= 2;
	cout << rn << " " << rm << "\n";
	for (int a : res) {
		cout << a << " ";
	}
	cout << "\n";
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED