图论new

边双连通分量

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n, m, cnt, ans, dfn[N], low[N]; //dfn记录dfs序，low表示这个点除树边外能连到最浅 
vector<int> mp[N], mp2[N];
vector<int> s;
void shuru() {int u, v;cin >> n >> m;for(int i = 1; i <= m; i++){cin >> u >> v;mp[u].push_back(v);mp[v].push_back(u);}
}
void dfs(int u, int f){dfn[u] = low[u] = ++cnt; //记录dfs序并初始化low int cnt = 0; //用来判重边 s.push_back(u);for(auto v : mp[u]){if(v == f && !cnt){cnt = 1; continue;	}if(!dfn[v]) dfs(v, u);low[u] = min(low[u], low[v]);//更新low }if(low[u] == dfn[u]){//把在一个连通分量的点染成一个颜色++ans; //增加一个连通分量 while(1) {int x = s.back();s.pop_back();mp2[ans].push_back(x);if(x == u) break; }		}
}
void shuchu(){cout << ans << endl;for(int i = 1; i <= ans; i++){cout << mp2[i].size() << " ";for(auto x : mp2[i]) cout << x << " ";cout << endl;}
}
int main(){shuru();for(int i = 1; i <= n; i++){if(dfn[i]) continue;dfs(i,i);}shuchu();return 0;
}

割点

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+5;
int n, m, cnt, tot, dfn[N], low[N], g[N];
vector<int> mp[N], v;
vector<int> s;
void shuru(){int u, v;cin >> n >> m;for(int i = 1; i <= m; i++){cin >> u >> v;if(u == v) continue; //特判自环 mp[u].push_back(v);mp[v].push_back(u);}
}
void dfs(int u, int f){dfn[u] = low[u] = ++cnt;for(auto v : mp[u]){if(v == f) continue;if(!dfn[v]){dfs(v, u);low[u] = min(low[u], low[v]);if(low[v] >= dfn[u]) g[u]++; //如果儿子的low比父亲还深，说明父亲是一个割点	}else low[u] = min(low[u], dfn[v]); //如果不是树边，就不会吃v==f的判断，用dfn判才不会影响判割点 }
}
int main(){shuru();for(int i = 1; i <= n; i++){if(dfn[i]) continue;dfs(i,i);g[i]--;//特判根节点 }for(int i = 1; i <= n; i++){if(g[i] > 0) v.push_back(i);}cout << v.size() << endl;for(auto x : v) cout << x << " ";return 0;
} 

点双连通分量

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n, m, cnt, ans, dfn[N], low[N];
vector<int> mp[N], mp2[N];
vector<int> s;
void shuru(){int u, v;cin >> n >> m;for(int i = 1; i <= m; i++){cin >> u >> v;if(u == v) continue;mp[u].push_back(v);mp[v].push_back(u);}
}
void dfs(int u, int f){ //本质就是找割点 if(u == f && mp[u].empty()) { //一个点也是点双连通分量，要特判 ++ans;mp2[ans].push_back(u);}dfn[u] = low[u] = ++cnt;s.push_back(u);for(auto v : mp[u]){if(v == f) continue;if(!dfn[v]){dfs(v, u);low[u] = min(low[u], low[v]);if(low[v] >= dfn[u]){ //类似于边双连通，用栈维护 ++ans;while(1){int x = s.back(); s.pop_back();mp2[ans].push_back(x);if(x == v) break; }mp2[ans].push_back(u); //要把割点本身放进去 }}else low[u] = min(low[u], dfn[v]); //类似割点特判 }
}
void shuchu(){cout << ans << endl;for(int i = 1; i <= ans; i++){cout << mp2[i].size() << " ";for(auto x : mp2[i]) cout << x << " ";cout << endl;}
}
int main(){shuru();for(int i = 1; i <= n; i++){if(dfn[i]) continue;dfs(i,i);}shuchu();return 0;
}