Untitled diff
创建于 差异永不过期
#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;
}
}