CF1037E图论思维（set::erase的用法）

╰+哭是因爲堅強的太久メ 2022-05-14 07:27 79阅读 0赞

[传送门][Link 1]

#include<bits/stdc++.h>
    using namespace std;
    #define fir first
    #define sec second
    const int N=2e5+10;
    typedef pair<int, int> pii;
    pii e[N];
    set<int> G[N];
    bool removed[N];
    int deg[N], ans[N], k;
    set<int> s;
    set<int>::iterator it;
    
    void _remove(int u){
    	queue<int> q;
    	q.push(u);
    	while(!q.empty()){
            int u=q.front(); q.pop();
            s.insert(u);
            //cout<<u<<endl;
            removed[u]=true;
            for(it=G[u].begin(); it!=G[u].end();){
                int v=*it;
                it++;//一定要自行++，因为erase之后it指针置空
                if(removed[v]) continue;
                G[v].erase(u);
                G[u].erase(v);
                deg[v]--;
                if(deg[v]<k)
                    q.push(v);
            }
    	}
    }
    
    int main(){
    	int n, m;
    	scanf("%d%d%d", &n, &m, &k);
    	for(int i=1; i<=m; i++){
    		scanf("%d%d", &e[i].fir, &e[i].sec);
    		G[e[i].fir].insert(e[i].sec);
    		G[e[i].sec].insert(e[i].fir);
    		deg[e[i].fir]++; deg[e[i].sec]++;
    	}
    
    	for(int i=1; i<=n; i++){
    		if(deg[i]<k && !removed[i]){
    			_remove(i);
    		}
    	}
    
    	ans[m]=n-s.size();
    	for(int i=m; i>1; i--){
    		int u=e[i].fir, v=e[i].sec;
    
    		if(!removed[u] && !removed[v]){
                deg[u]--; deg[v]--;
                G[u].erase(v); G[v].erase(u);
                if(deg[u]<k) _remove(u);
                if(deg[v]<k) _remove(v);
    		}
    
    		ans[i-1]=n-s.size();
    	}
    	for(int i=1; i<=m; i++)
    		printf("%d\n", ans[i]);
    
    	return 0;
    }

[Link 1]: http://codeforces.com/contest/1037/problem/E

发表评论取消回复

表情：

评论列表（有 0 条评论，79人围观）

还没有评论，来说两句吧...

相关阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 71 阅读

相关【简单图论】CF1833 E

[Problem - E - Codeforces][] 题意： ![e5307033af4e492996bee444f2c9fecf.png][] ![0ee52ece

￡神魔★判官ぃ/ 2024年03月22日 19:53/ 0 赞/ 80 阅读

相关【组合数学+插板法】CF893E

[Problem - 893E - Codeforces][] 题意： ![9b8b18625f244323a91936f7d4464fcc.png][] 思路： ![

清疚/ 2024年03月16日 11:07/ 0 赞/ 46 阅读

相关【简单图论】CF898 div4 H

[Problem - H - Codeforces][] 题意： ![4b37a99e5b464ba681c364f7b47a7a52.png][] 思路：手玩一下样

爱被打了一巴掌/ 2024年03月01日 01:46/ 0 赞/ 80 阅读

相关 CF891E Lust

CF891E Lust -------------------- 鸽子更博了 Orz Itst 神仙结论：最后的答案是一开始的\\(\\prod a\_i\\)减去

迈不过友情╰/ 2023年08月17日 17:29/ 0 赞/ 118 阅读

相关 CF1037E图论思维（set::erase的用法）

[传送门][Link 1] include<bits/stdc++.h> using namespace std; define fir first

╰+哭是因爲堅強的太久メ/ 2022年05月14日 07:27/ 0 赞/ 80 阅读

相关 [CF1111E]Tree

题目大意：给一棵$n(n\\leqslant10^5)$个点的树，有$q(q\\leqslant10^5)$次询问，每次询问给出$k,m,r$表示把以下$k$个点分成不超过$m

素颜马尾好姑娘i/ 2021年12月22日 04:15/ 0 赞/ 210 阅读

相关 CF 166E Tetrahedron

E. Tetrahedron time limit per test 2 seconds memory limit per test 256 megabytes in

蔚落/ 2021年12月19日 14:35/ 0 赞/ 209 阅读

相关 cf 1009E

如何看待某cf2000分选手不会一道tag1900的题？难。考虑每段距离的贡献， a\[i\]出现在位置j上，当且仅当j-i休息，并且中间的都不是休息的。

曾经终败给现在/ 2021年10月25日 12:56/ 0 赞/ 265 阅读

相关 E1. Square-free division (easy version) (数论、思维)

[题目][Link 1] 思路：首先贪心的想一想，我让每一段尽可能长，则最后的段数就可能越少。再来看什么时候一个数是平方数，将一个数质因数分解 X=a^x1

末蓝、/ 2021年07月16日 15:21/ 0 赞/ 367 阅读