Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 50005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- int n, m;
- vector<ii> g[N];
- int cau[100005];
- int num[N], low[N], cnt;
- vector<int> g2[N];
- vector<int> g3[N];
- struct edge{
- int u, v;
- } e[100005];
- int root;
- int st[100005];
- int sn;
- int tplt;
- int dai_dien[10005];
- int head[10005];
- void dfs(int u, int pre){
- num[u] = low[u] = ++cnt;
- for(auto i : g[u]){
- int v = i.fi;
- int id = i.se;
- if (v==pre) continue;
- if (num[v]) low[u] = min(low[u],num[v]);
- else{
- dfs(v,u);
- low[u] = min(low[u],low[v]);
- if (low[v]>=num[v]){
- cau[id] = 1;
- }
- }
- }
- }
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n >> m;
- for(int i=1; i<=m; i++){
- int u, v;
- cin >> u >> v;
- g[u].pb(ii(v,i));
- g[v].pb(ii(u,i));
- e[i] = {u,v};
- }
- }
- void DFS(int u){
- dai_dien[u] = tplt;
- for(auto v : g2[u]){
- if (!dai_dien[v]){
- DFS(v);
- }
- }
- }
- vector<int> leaf;
- void DFS_arrange(int u, int pre){
- for(auto v : g3[u]){
- if (v!=pre){
- DFS_arrange(v,u);
- }
- }
- if (g3[u].size()==1 && u!=1) leaf.pb(u);
- }
- void proc()
- {
- for(int i=1; i<=n; i++){
- if (num[i]==0){
- dfs(i,i);
- }
- }
- for(int i=1; i<=m; i++){
- if (!cau[i]){
- int u = e[i].u;
- int v = e[i].v;
- g2[u].pb(v);
- g2[v].pb(u);
- }
- }
- for(int i=1; i<=n; i++){
- if (!dai_dien[i]){
- ++tplt;
- head[tplt] = i;
- DFS(i);
- }
- }
- for(int i=1; i<=n; i++){
- int u = dai_dien[i];
- for(auto j : g[i]){
- int v = j.fi;
- v = dai_dien[v];
- if (u!=v){
- g3[u].pb(v);
- g3[v].pb(u);
- }
- }
- }
- for(int i=1; i<=tplt; i++){
- if (g3[i].size()){
- sort(all(g3[i]));
- g3[i].erase(unique(all(g3[i])),g3[i].end());
- }
- }
- // phần này là nối nè gs :v phần trên đệ nén đồ thị
- vector<ii> res;
- DFS_arrange(1,1);
- for(auto x : leaf){
- if (sn < 3){
- st[++sn] = x;
- }
- if (sn==3){
- int u = head[st[1]];
- int v = head[st[3]];
- res.pb(ii(u,v));
- st[1] = st[2];
- sn = 1;
- }
- }
- if (sn==2){
- res.pb(ii(head[st[1]],head[st[2]]));
- }
- if (sn==1 || g3[1].size()==1){
- res.pb(ii(head[st[1]],1));
- }
- cout << res.size() << '\n';
- for(auto tmp : res) cout << tmp.fi << ' ' << tmp.se << '\n';
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Add Comment
Please, Sign In to add comment