Comparing sensitive data, confidential files or internal emails?

Most legal and privacy policies prohibit uploading sensitive data online. Diffchecker Desktop ensures your confidential information never leaves your computer. Work offline and compare documents securely.

Untitled diff

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