【补题】Codeforces Round 954 (Div. 3) F. Non-academic Problem

题意：给出一个连通图，n个点m条边，问给你一次操作，可以删除任何一条边，问删除之后，让两个点之间不可以互相抵达的对数最少，是多少

前置知识：
1.tarjan算法，tarjan缩点D14【模板】强连通分量 Tarjan 算法——信息学奥赛算法_哔哩哔哩_bilibili
D15 Tarjan SCC 缩点_哔哩哔哩_bilibili
2.边双连通分量
【学习】P8436 【模板】边双连通分量 Tarjan判边双连通分量-CSDN博客
P8436 【模板】边双连通分量 - 洛谷

思路：题解：CF1986F Non-academic Problem - 洛谷专栏

1.如果不会tarjan算法，应该是做不了的，关键就是他求删除某条边要让一些点之间互相不能抵达，而删除某条边依旧能保持连接的点就是边双连通分量，因此如果我们得到所有的边双连通分量并进行缩点之后，题目给出的图其实就变成了一棵边双连通分量组成的树。
如果你不明白，那就去学习前置知识点，你会发现这道题近乎接近板子

2.这里并不使用割点做，因为你转化成了树之后了，其实无非就是删去那条边（桥），会分成上下层或者左右层，所以进行dfs递归得到每个边的一块区域子树，另外一块其实就是n-siz，少掉的部分就是siz*(n-siz)，这样代码也简单
记录最大的删除对数，反过来计算剩余的最小的保留对数，这道题就完成了

挺不错的偏板子的题目，很适合学习taijan和边双连通分量，完成模板之后来做这一道题很赞

关于代码：
1.代码中没有使用instk，也就是记录是否在栈中，这是因为是无向图，没有有向图搜索树的横叉边，不会出现，可以改用else
2.重新建图的时候也是无向图
3.重现建图用了set，单纯vector是会错的，因为边双连通分量里面可能有很多条边连接了不同的分量，这里直接使用set去重了，否则会计算错误子树的点的数量

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS                       \
	std::ios::sync_with_stdio(0); \
	std::cin.tie(0);              \
	std::cout.tie(0)

const int N = 3e5 + 5;
const int INF = 1e18;
const int MOD = 998244353;
// const int MOD=1e9+7;
// const int MOD=100003;
const int maxn=5e5+10;

std::vector<int> ve[N];
int dfn[N],low[N];
int scc[N],siz[N];
int cnt,tot;
std::stack<int> st;
int n,m;

void tarjan(int x,int fa){
    dfn[x]=low[x]=++cnt;
    st.push(x);
    for(auto u : ve[x]){
        if(u==fa) continue;
        if(!dfn[u]){
            tarjan(u,x);
            low[x]=std::min(low[x],low[u]);
        }
        else{
            low[x]=std::min(low[x],dfn[u]);
        }
    }
    if(dfn[x]==low[x]){
        int y;++tot;
        do{
            y=st.top();
            st.pop();
            scc[y]=tot;
            siz[tot]++;
        }while(y!=x);
    }
}

std::set<int> ne[N];
int res=0;
int dfs(int x,int fa){

    int now=siz[x];
    for(auto u : ne[x]){
        if(u==fa) continue;
        now+=dfs(u,x);
    }
    res=std::max(res,now*(n-now));
    return now;
}

void init(){
    cnt=0;res=0;tot=0;
    for(int i=1;i<=n;i++){
        ve[i].clear();
        ne[i].clear();
        dfn[i]=0;low[i]=0;scc[i]=0;siz[i]=0;
    }
}

void solve(){
    
    std::cin >> n >> m;
    init();

    for(int i=0;i<m;i++){
        int x,y;
        std::cin >> x >> y;
        ve[x].push_back(y);
        ve[y].push_back(x);
    }

    for(int i=1;i<=n;i++){
        tarjan(i,0);
    }

    for(int i=1;i<=n;i++){
        for(auto j : ve[i]){   
            if(scc[i]!=scc[j]){
                ne[scc[i]].insert(scc[j]);
                ne[scc[j]].insert(scc[i]);
            }
        }
    }

    dfs(1,0);

    std::cout << (n*(n-1)/2)-res << '\n';
}

signed main()
{
	IOS;

	int t = 1;
	std::cin >> t;
	while (t--)
	{
		solve();
	}
}