9625 | 2024. 02. 23 15:21:06 | zeytonx | Hálózati biztonság (50) | cpp17 | Elfogadva 50/50 | 86ms | 24256 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef set<ll> sll;
typedef queue<ll> qll;
typedef priority_queue<ll> pqll;
typedef vector<vll> v2ll;
typedef map<ll,ll> mll;
typedef vector<pll> vpll;
typedef map<pll,ll> mpll;
#define fs first
#define sc second
#define pb push_back
const ll MOD = 1e9+7;
void solve()
{
ll n, m, k;
cin >> n >> m >> k;
v2ll g(n);
vll rc(n, 0);
for(ll i = 0; i < m; i++)
{
ll a, b;
cin >> a >> b;
a--; b--;
g[a].pb(b);
g[b].pb(a);
}
qll q;
vll used(n, 0);
for(ll i = 0; i < n; i++)
{
rc[i] = g[i].size();
if(rc[i] < k)
{
q.push(i);
used[i] = 1;
}
}
while(!q.empty())
{
ll p = q.front();
used[p] = 2;
q.pop();
for(ll i : g[p])
{
if(used[i] != 2)
{
if(rc[i] >= k)
rc[i]--;
if(rc[i] < k && used[i] == 0)
{
q.push(i);
used[i] = 1;
}
}
}
}
sll ans;
for(ll i = 0; i < n; i++)
if(rc[i] >= k)
ans.insert(i);
cout << ans.size() << "\n";
for(ll i : ans)
cout << i+1 << " ";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
ll t = 1;
//cin >> t;
while(t--)
solve();
cout << endl;
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1824 KiB | |||
2 | Elfogadva | 0/0 | 46ms | 12880 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2392 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2604 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2924 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2868 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 3012 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 2992 KiB | |||
9 | Elfogadva | 2/2 | 3ms | 3108 KiB | |||
10 | Elfogadva | 2/2 | 6ms | 3912 KiB | |||
11 | Elfogadva | 2/2 | 3ms | 3540 KiB | |||
12 | Elfogadva | 2/2 | 4ms | 4100 KiB | |||
13 | Elfogadva | 3/3 | 3ms | 3812 KiB | |||
14 | Elfogadva | 3/3 | 4ms | 4640 KiB | |||
15 | Elfogadva | 3/3 | 7ms | 5804 KiB | |||
16 | Elfogadva | 3/3 | 46ms | 11652 KiB | |||
17 | Elfogadva | 3/3 | 6ms | 4360 KiB | |||
18 | Elfogadva | 3/3 | 9ms | 9056 KiB | |||
19 | Elfogadva | 3/3 | 54ms | 20068 KiB | |||
20 | Elfogadva | 3/3 | 86ms | 24256 KiB | |||
21 | Elfogadva | 3/3 | 54ms | 20956 KiB | |||
22 | Elfogadva | 3/3 | 3ms | 4160 KiB |