Comparar texto

Encuentra la diferencia entre dos archivos de texto

Editor live

Ocultar sin cambios

Sin ajuste de línea

Vista

Nivel de detalle

Resaltado de sintaxis

Diffchecker Desktop La forma más segura de usar Diffchecker. ¡Obtén la app de Diffchecker Desktop: tus diffs nunca salen de tu computadora!Obtener Desktop

Untitled diff

Creado hace 11 añosEl diff nunca expira

0 eliminaciones

Líneas
Total
Eliminado

Caracteres
Total
Eliminado

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

101 líneas

3 adiciones

Líneas
Total
Añadido

Caracteres
Total
Añadido

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

104 líneas

#include <iostream>

#include <cstring>

#include <vector>

#include <set>

using namespace std;

const int MAX = 100005;

vector<int> adj[MAX];

long long ver[MAX], num[MAX], den[MAX];

int n, m, k;

bool mark[MAX];

bool cmp(pair<long long, long long> a, pair<long long, long long> b)

{

return (a.first * b.second < a.second * b.first);

}

struct cmpp

{

bool operator ()(pair<pair<long long, long long>, int> l, pair<pair<long long, long long>, int> r)

{

if (cmp(l.first, r.first))

return true;

if (cmp(r.first, l.first))

return false;

return (l.second < r.second);

}

};

set<pair<pair<long long, long long>, int>, cmpp> s;

pair<long long, long long> ans;

void go(pair<long long, long long> lim)

{

memset(mark, false, sizeof(mark));

for (int i = 0; i < k; i++)

mark[ver[i]] = true;

s.clear();

for (int v = 0; v < n; v++)

if (!mark[v])

{

num[v] = den[v] = 0;

for (int i = 0; i < adj[v].size(); i++)

{

int u = adj[v][i];

den[v]++;

if (!mark[u])

num[v]++;

}

if (num[v] < den[v])

s.insert(make_pair(make_pair(num[v], den[v]), v));

}

while (!s.empty())

{

int v = s.begin()->second;

s.erase(s.begin());

if (cmp(ans, make_pair(num[v], den[v])))

ans = make_pair(num[v], den[v]);

if (!cmp(make_pair(num[v], den[v]), lim))

break;

mark[v] = true;

for (int i = 0; i < adj[v].size(); i++)

{

int u = adj[v][i];

if (!mark[u])

{

s.erase(make_pair(make_pair(num[u], den[u]), u));

num[u]--;

s.insert(make_pair(make_pair(num[u], den[u]), u));

}

for (int i = 0; i < n; i++)

if (!mark[i])

ans = make_pair(1, 1);

}

int main()

{

ios::sync_with_stdio(false);

ans.first = 0;

ans.second = 1;

cin >> n >> m >> k;

for (int i = 0; i < k; i++)

{

cin >> ver[i];

ver[i]--;

}

for (int i = 0; i < m; i++)

{

int u, v;

cin >> u >> v;

u--;

v--;

adj[u].push_back(v);

adj[v].push_back(u);

}

go(make_pair(2, 1));

go(ans);

int cnt = 0;

for (int i = 0; i < n; i++)

if (!mark[i])

cnt++;

cout << cnt << endl;

for (int i = 0; i < n; i++)

if (!mark[i])

cout << i + 1 << " ";

cout << endl;

return 0;

}

Diferencias guardadas

Texto original

Abrir archivo

#include <iostream>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
const int MAX = 100005;
vector<int> adj[MAX];
long long ver[MAX], num[MAX], den[MAX];
int n, m, k;
bool mark[MAX];
bool cmp(pair<long long, long long> a, pair<long long, long long> b)
{
	return (a.first * b.second < a.second * b.first);
}
struct cmpp
{
	bool operator ()(pair<pair<long long, long long>, int> l, pair<pair<long long, long long>, int> r)
	{
		if (cmp(l.first, r.first))
			return true;
		if (cmp(r.first, l.first))
			return false;
		return (l.second < r.second);
	}
};
set<pair<pair<long long, long long>, int>, cmpp> s;
pair<long long, long long> ans;
void go(pair<long long, long long> lim)
{
	memset(mark, false, sizeof(mark));
	for (int i = 0; i < k; i++)
		mark[ver[i]] = true;
	s.clear();
	for (int v = 0; v < n; v++)
		if (!mark[v])
		{
			num[v] = den[v] = 0;
			for (int i = 0; i < adj[v].size(); i++)
			{
				int u = adj[v][i];
				den[v]++;
				if (!mark[u])
					num[v]++;
			}
			if (num[v] < den[v])
				s.insert(make_pair(make_pair(num[v], den[v]), v));
		}
	while (!s.empty())
	{
		int v = s.begin()->second;
		s.erase(s.begin());
		if (cmp(ans, make_pair(num[v], den[v])))
			ans = make_pair(num[v], den[v]);
		if (!cmp(make_pair(num[v], den[v]), lim))
			break;
		mark[v] = true;
		for (int i = 0; i < adj[v].size(); i++)
		{
			int u = adj[v][i];
			if (!mark[u])
			{
				s.erase(make_pair(make_pair(num[u], den[u]), u));
				num[u]--;
				s.insert(make_pair(make_pair(num[u], den[u]), u));
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	ans.first = 0;
	ans.second = 1;
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++)
	{
		cin >> ver[i];
		ver[i]--;
	}
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	go(make_pair(2, 1));
	go(ans);
	int cnt = 0;
	for (int i = 0; i < n; i++)
		if (!mark[i])
			cnt++;
	cout << cnt << endl;
	for (int i = 0; i < n; i++)
		if (!mark[i])
			cout << i + 1 << " ";
	cout << endl;
	return 0;
}

Texto modificado

Abrir archivo

#include <iostream>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
const int MAX = 100005;
vector<int> adj[MAX];
long long ver[MAX], num[MAX], den[MAX];
int n, m, k;
bool mark[MAX];
bool cmp(pair<long long, long long> a, pair<long long, long long> b)
{
	return (a.first * b.second < a.second * b.first);
}
struct cmpp
{
	bool operator ()(pair<pair<long long, long long>, int> l, pair<pair<long long, long long>, int> r)
	{
		if (cmp(l.first, r.first))
			return true;
		if (cmp(r.first, l.first))
			return false;
		return (l.second < r.second);
	}
};
set<pair<pair<long long, long long>, int>, cmpp> s;
pair<long long, long long> ans;
void go(pair<long long, long long> lim)
{
	memset(mark, false, sizeof(mark));
	for (int i = 0; i < k; i++)
		mark[ver[i]] = true;
	s.clear();
	for (int v = 0; v < n; v++)
		if (!mark[v])
		{
			num[v] = den[v] = 0;
			for (int i = 0; i < adj[v].size(); i++)
			{
				int u = adj[v][i];
				den[v]++;
				if (!mark[u])
					num[v]++;
			}
			if (num[v] < den[v])
				s.insert(make_pair(make_pair(num[v], den[v]), v));
		}
	while (!s.empty())
	{
		int v = s.begin()->second;
		s.erase(s.begin());
		if (cmp(ans, make_pair(num[v], den[v])))
			ans = make_pair(num[v], den[v]);
		if (!cmp(make_pair(num[v], den[v]), lim))
			break;
		mark[v] = true;
		for (int i = 0; i < adj[v].size(); i++)
		{
			int u = adj[v][i];
			if (!mark[u])
			{
				s.erase(make_pair(make_pair(num[u], den[u]), u));
				num[u]--;
				s.insert(make_pair(make_pair(num[u], den[u]), u));
			}
		}
	}
	for (int i = 0; i < n; i++)
		if (!mark[i])
			ans = make_pair(1, 1);
}
int main()
{
	ios::sync_with_stdio(false);
	ans.first = 0;
	ans.second = 1;
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++)
	{
		cin >> ver[i];
		ver[i]--;
	}
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	go(make_pair(2, 1));
	go(ans);
	int cnt = 0;
	for (int i = 0; i < n; i++)
		if (!mark[i])
			cnt++;
	cout << cnt << endl;
	for (int i = 0; i < n; i++)
		if (!mark[i])
			cout << i + 1 << " ";
	cout << endl;
	return 0;
}