比赛的时候想到怎么做了 没调出来(感觉自己是个睿智)
给你N个点M条边,这M条边是一条一条加进去的 要求你求出加入每一条边时图中极大'K度'子图的大小
极大'K度'子图的意思是 要求出一个有尽量多的点的子图 该图中每个点的度数至少为K
因为他每加一条边只会影响到两个点的度数 所以很明显下一个极大'K度'子图是在上一个的基础上得来的
所以如果我们知道在最早哪一步加入边时 产生了极大'K度'子图的话 我们就可以对每条边进行判定得出答案
但是如果每一步都判是否有极大'K度'子图 肯定会超时 该题是离线询问 所以可以考虑倒着做
先把M条边全部加进去 再拓扑排序 每次POP出一个度数小于K的节点 在图中删掉他所连的边 直至队列为空
得出了ans[M] 我们倒着枚举处理每条边即可
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
vector<int> tree[];
pair<int, int> edge[];
int ans[];
int du[];
queue<int> que;
bool vis[];
map<pair<int, int>, int> mp;
int main()
{
ios_base::sync_with_stdio();
cin.tie(); int n, m, k;
int u, v;
cin >> n >> m >> k;
for (int i = ; i <= m; i++)
{
cin >> u >> v;
edge[i].first = u, edge[i].second = v;
du[v]++, du[u]++;
tree[u].pb(v), tree[v].pb(u);
}
for (int i = ; i <= n; i++)
{
if (du[i] < k)
{
que.push(i);
vis[i] = true;
}
}
while (que.size())
{
int now = que.front();
que.pop();
for (auto v : tree[now])
{
if (mp[make_pair(now, v)])
{
continue;
}
du[v]--;
mp[make_pair(now, v)] = mp[make_pair(v, now)] = ;
if (du[v] < k && (!vis[v]))
{
vis[v] = true;
que.push(v);
}
}
}
for (int i = ; i <= n; i++)
{
if (!vis[i])
{
ans[m]++;
}
}
for (int i = m - ; i >= ; i--)
{
ans[i] = ans[i + ];
u = edge[i + ].first, v = edge[i + ].second;
if (mp[make_pair(u, v)])
{
continue;
}
du[u]--, du[v]--;
mp[make_pair(u, v)] = mp[make_pair(v, u)] = ;
if (du[u] < k && (!vis[u]))
{
vis[u] = true;
que.push(u);
ans[i]--;
}
if (du[v] < k && (!vis[v]))
{
vis[v] = true;
que.push(v);
ans[i]--;
}
while (que.size())
{
int now = que.front();
que.pop();
for (auto v : tree[now])
{
if (mp[make_pair(now, v)])
{
continue;
}
du[v]--;
mp[make_pair(now, v)] = mp[make_pair(v, now)] = ;
if (du[v] < k && (!vis[v]))
{
ans[i]--;
vis[v] = true;
que.push(v);
}
}
}
}
for (int i = ; i <= m; i++)
{
cout << ans[i] << endl;
}
return ;
}
//E.Trips