B. 0-1 MST
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Ujan has a lot of useless stuff in his drawers, a considerable part of which are his math notebooks: it is time to sort them out. This time he found an old dusty graph theory notebook with a description of a graph.
It is an undirected weighted graph on n vertices. It is a complete graph: each pair of vertices is connected by an edge. The weight of each edge is either 0 or 1; exactly m edges have weight 1, and all others have weight 0.
Since Ujan doesn’t really want to organize his notes, he decided to find the weight of the minimum spanning tree of the graph. (The weight of a spanning tree is the sum of all its edges.) Can you find the answer for Ujan so he stops procrastinating?
Input
The first line of the input contains two integers n and m (1≤n≤105 , 0≤m≤min(n(n−1)/2,105)), the number of vertices and the number of edges of weight 1 in the graph.
The i-th of the next m lines contains two integers ai and bi (1≤ai,bi≤n, ai≠bi), the endpoints of the i-th edge of weight 1.
It is guaranteed that no edge appears twice in the input.
Output
Output a single integer, the weight of the minimum spanning tree of the graph.
Examples
input
6 11 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6
output
2
input
3 0
output
0
Note
The graph from the first sample is shown below. Dashed edges have weight 0, other edges have weight 1. One of the minimum spanning trees is highlighted in orange and has total weight 2.
In the second sample, all edges have weight 0 so any spanning tree has total weight 0.
题目大意
给定一张带权的无向完全图，每条边的边权为1或者是0，图中包含n个点，再所有的边中，有m条边的边权为1，其余的边权为0
输出图的最小生成树的权值
思路
从数据范围的角度来看，如果正向考虑，估计不太可能
可以从反方向思考
我们的目标是求得最小的生成树，就要用到最少的1，最多的0
因此我们可以从这样的方式出发：
找到联通的0的联通块的个数，比如说有cnt个，那么为了将这些连通块连通起来形成最小生成树就要添上边权为1的边来进行连接，因此答案就是补图的连通块的个数-1
联通的0的块数不会对答案产生贡献，且一个边权全为0的连通块内一定可以形成产生生成树，边权为1的边只有对连通块进行连接的作用，对于cnt个连通块，只需要cnt-1条边权为1的边进行连接即可
所以说关键一点就是求补图的连通块
在存边的时候，我们可以考虑用map进行标记这条边是0边还是1边
边足够多的情况下，我们可以考虑从点的角度进行出发（进行bfs），对于这n个点，我们用set进行维护，一旦某个点被访问过，就将这个点从set集合中进行删除操作，
将给出的边权为1的边进行标记，在访问某一个点的过程中，我们只需要考虑当前节点与set中存在的点中边权为0的点，并且没有被标记过的点进行操作即可
在遍历set集合的过程中，可以先将符合条件的点放在vector中，在bfs结束之后进行统一删除，如果在遍历的过程中删除的话，可能会出现re
如果有不严谨的地方还请多多指教
upd: 考虑复杂度均摊以下的话应该是(n + m) * log n
如果说全为1的边的情况，最大是1e5 ，点不会超过1e3,复杂度为n^2 logn，可以过
下面放上主要代码
int n, m, k; map<int,bool> mp[maxn]; set<int> st; set<int> gra[maxn]; bool vis[maxn]; void bfs(int x) { queue<int>que; que.push(x); ///vis[x] = 1; st.erase(x); while(que.size()) { /// int u = que.front(); que.pop(); vis[u] = 1; vector<int>vet; for(set<int>::iterator it = st.begin(); it!=st.end(); it++) { ///auto at:st ///cout<<"## "<<at<<endl; int at = *it; if(gra[at].count(u) == 0) { ///no edge connected ///st.erase(at);/// RE!!! vet.push_back(at); ///vis[at] = 1; que.push(at); } } for(int i=0;i<vet.size();i++){ st.erase(vet[i]); } } } int main() { int n,m; memset(vis,0,sizeof vis); cin >> n >> m; st.clear(); for(int i=1; i<=n; i++) { st.insert(i); } for(int i=1; i<=m; i++) { int u=read,v=read; gra[u].insert(v); gra[v].insert(u); } int cnt = 0; for(int i=1; i<=n; i++) { if(vis[i] == 0) { bfs(i); cnt ++; } } cout<<cnt-1<<'\n'; return 0; }
再放上一份大同小异的代码：
只是加标记的位置不同罢了
const int maxn = 2e5 + 7; int n, m, k; map<int,bool> mp[maxn]; set<int> st; set<int> gra[maxn]; bool vis[maxn]; void bfs(int x) { queue<int>que; que.push(x); vis[x] = 1; st.erase(x); while(que.size()) { /// int u = que.front(); que.pop(); ///vis[u] = 1; vector<int>vet; for(set<int>::iterator it = st.begin(); it!=st.end(); it++) { ///auto at:st ///cout<<"## "<<at<<endl; int at = *it; if(gra[at].count(u) == 0) { ///no edge conneceted ///st.erase(at); vet.push_back(at); vis[at] = 1; que.push(at); } } for(int i=0;i<vet.size();i++){ st.erase(vet[i]); } } } int main() { int n,m; memset(vis,0,sizeof vis); cin >> n >> m; st.clear(); for(int i=1; i<=n; i++) { st.insert(i); } for(int i=1; i<=m; i++) { int u=read,v=read; gra[u].insert(v); gra[v].insert(u); } int cnt = 0; for(int i=1; i<=n; i++) { if(vis[i] == 0) { bfs(i); cnt ++; } } cout<<cnt-1<<'\n'; return 0; }
下面是用bitset操作的奇技淫巧：
const int maxn = 2e5 + 7; int n, m, k; int a[maxn]; map<int,bool> mp[maxn]; bitset<maxn>st; void dfs(int x) { st[x] = 0; for (int i = st._Find_first(); i < st.size(); i = st._Find_next(i)) { if(!mp[x][i]) { ///cout<<"IIII: "<<i<<endl; dfs(i); } } } int main() { int n,m; cin >> n >> m; for(int i=1;i<=n;i++){ st[i] = 1; } for(int i=1;i<=m;i++){ int u=read,v=read; mp[u][v] = mp[v][u] = 1; } int cnt = 0; for(int i=1;i<=n;i++){ if(st[i]){ ///cout<<"###"<<st[i]<<endl; dfs(i); cnt ++; } } cout<<cnt-1<<'\n'; return 0; }
![[Nowcoder] network | Tarjan 边双连通分量 | 缩点 | LCA倍增优化 | 并查集](https://ucc.alicdn.com/pic/developer-ecology/5554eff79239411c8300cad4838b1fe7.png?x-oss-process=image/resize,h_160,m_lfit)