Texte vergleichen

Finde den Unterschied zwischen zwei Textdateien

Live-Editor

Gleiches ausblenden

Zeilenumbruch aus

Ansicht

Vergleichsgenauigkeit

Syntaxhervorhebung

Diffchecker Desktop Der sicherste Weg, Diffchecker zu nutzen. Hol dir die Desktop-App: Deine Diffs verlassen nie deinen Computer!Desktop holen

Untitled diff

Erstellt vor 11 JahrenDiff läuft nie ab

0 Entfernungen

Zeilen
Gesamt
Entfernt

Zeichen
Gesamt
Entfernt

Um diese Funktion weiterhin zu nutzen, aktualisiere auf Diffchecker Pro Preise anzeigen

101 Zeilen

3 Hinzufügungen

Zeilen
Gesamt
Hinzugefügt

Zeichen
Gesamt
Hinzugefügt

Um diese Funktion weiterhin zu nutzen, aktualisiere auf Diffchecker Pro Preise anzeigen

104 Zeilen

#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;

}

Gespeicherte Diffs

Originaltext

Datei öffnen

#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;
}

Bearbeitung

Datei öffnen

#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;
}