Codeforces Manthan, Codefest 18 (rated, Div. 1 + Div. 2) E.Trips

比赛的时候想到怎么做了没调出来(感觉自己是个睿智)

给你N个点M条边,这M条边是一条一条加进去的要求你求出加入每一条边时图中极大'K度'子图的大小

极大'K度'子图的意思是要求出一个有尽量多的点的子图该图中每个点的度数至少为K

因为他每加一条边只会影响到两个点的度数所以很明显下一个极大'K度'子图是在上一个的基础上得来的

所以如果我们知道在最早哪一步加入边时产生了极大'K度'子图的话我们就可以对每条边进行判定得出答案

但是如果每一步都判是否有极大'K度'子图肯定会超时该题是离线询问所以可以考虑倒着做

先把M条边全部加进去再拓扑排序每次POP出一个度数小于K的节点在图中删掉他所连的边直至队列为空

得出了ans[M] 我们倒着枚举处理每条边即可

  1 /*Huyyt*/
  2 #include<bits/stdc++.h>
  3 #define mem(a,b) memset(a,b,sizeof(a))
  4 #define pb push_back
  5 using namespace std;
  6 typedef long long ll;
  7 typedef unsigned long long ull;
  8 using namespace std;
  9 vector<int> tree[200005];
 10 pair<int, int> edge[200005];
 11 int ans[200005];
 12 int du[200005];
 13 queue<int> que;
 14 bool vis[200005];
 15 map<pair<int, int>, int> mp;
 16 int main()
 17 {
 18         ios_base::sync_with_stdio(0);
 19         cin.tie(0);
 20 
 21         int n, m, k;
 22         int u, v;
 23         cin >> n >> m >> k;
 24         for (int i = 1; i <= m; i++)
 25         {
 26                 cin >> u >> v;
 27                 edge[i].first = u, edge[i].second = v;
 28                 du[v]++, du[u]++;
 29                 tree[u].pb(v), tree[v].pb(u);
 30         }
 31         for (int i = 1; i <= n; i++)
 32         {
 33                 if (du[i] < k)
 34                 {
 35                         que.push(i);
 36                         vis[i] = true;
 37                 }
 38         }
 39         while (que.size())
 40         {
 41                 int now = que.front();
 42                 que.pop();
 43                 for (auto v : tree[now])
 44                 {
 45                         if (mp[make_pair(now, v)])
 46                         {
 47                                 continue;
 48                         }
 49                         du[v]--;
 50                         mp[make_pair(now, v)] = mp[make_pair(v, now)] = 1;
 51                         if (du[v] < k && (!vis[v]))
 52                         {
 53                                 vis[v] = true;
 54                                 que.push(v);
 55                         }
 56                 }
 57         }
 58         for (int i = 1; i <= n; i++)
 59         {
 60                 if (!vis[i])
 61                 {
 62                         ans[m]++;
 63                 }
 64         }
 65         for (int i = m - 1; i >= 1; i--)
 66         {
 67                 ans[i] = ans[i + 1];
 68                 u = edge[i + 1].first, v = edge[i + 1].second;
 69                 if (mp[make_pair(u, v)])
 70                 {
 71                         continue;
 72                 }
 73                 du[u]--, du[v]--;
 74                 mp[make_pair(u, v)] = mp[make_pair(v, u)] = 1;
 75                 if (du[u] < k && (!vis[u]))
 76                 {
 77                         vis[u] = true;
 78                         que.push(u);
 79                         ans[i]--;
 80                 }
 81                 if (du[v] < k && (!vis[v]))
 82                 {
 83                         vis[v] = true;
 84                         que.push(v);
 85                         ans[i]--;
 86                 }
 87                 while (que.size())
 88                 {
 89                         int now = que.front();
 90                         que.pop();
 91                         for (auto v : tree[now])
 92                         {
 93                                 if (mp[make_pair(now, v)])
 94                                 {
 95                                         continue;
 96                                 }
 97                                 du[v]--;
 98                                 mp[make_pair(now, v)] = mp[make_pair(v, now)] = 1;
 99                                 if (du[v] < k && (!vis[v]))
100                                 {
101                                         ans[i]--;
102                                         vis[v] = true;
103                                         que.push(v);
104                                 }
105                         }
106                 }
107         }
108         for (int i = 1; i <= m; i++)
109         {
110                 cout << ans[i] << endl;
111         }
112         return 0;
113 }

//E.Trips