Codeforces Round 954 (Div. 3) F. Non-academic Problem

思路：考虑缩点，因为是无向图，所以双连通分量缩完点后是一棵树，我们去枚举删除每一条树边的答案，然后取最小值即可。

#include <bits/stdc++.h>

using namespace std;
const int N = 3e5 + 5;
typedef long long ll;
typedef pair<int,int> pll;
typedef array<ll, 3> ar;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"

int n,m;
vector<pll> e[N];
vector<int> e2[N];
vector<vector<int> > vdcc;
int dfsn[N],low[N],tot,b[N],sz[N];
stack<int> s;


void add(int u,int v,int i)
{
e[u].push_back({v,i});
e[v].push_back({u,i});
}

void tarjan(int x,int f)//tarjan 求边双连通分量
{
dfsn[x]=low[x]=++tot,s.push(x);
for(auto [u,i]: e[x]){
if(!dfsn[u]){
tarjan(u,i);
low[x]=min(low[x],low[u]);
}
else if(f!=i) low[x]=min(low[x],dfsn[u]);
}
if(dfsn[x]==low[x]){
vector<int> c;
while(1){
auto t=s.top();
b[t]=vdcc.size();
            sz[vdcc.size()]++;
c.push_back(t);
s.pop();
if(t==x) break;
}
vdcc.push_back(c);
}
}

void init()
{
    tot=0;
    for(int i=0;i<=n;i++){
        e[i].clear();
        e2[i].clear();
        dfsn[i]=b[i]=sz[i]=low[i]=0;
    }
    vdcc.clear();
    
}


ll ans=1e18;

int dfs(int x,int f)
{
    ll sum=0;
    for(auto u: e2[x]){
        if(u!=f) sum+=dfs(u,x);
    }
    sum+=sz[x];
    ll res=n-sum;
    ans=min(ans,(sum)*(sum-1)/2+(res-1)*res/2);
    return sum;
}


void solve()
{
    cin>>n>>m;
    init();
    ans=1e18;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,i);
    }
    for(int i=1;i<=n;i++){
        if(!dfsn[i]) tarjan(i,-1);
    }
    for(int i=1;i<=n;i++){
        for(auto [j,id]: e[i]){
            if(b[i]!=b[j]){
                e2[b[i]].push_back(b[j]);
                // e2[b[j]].push_back(b[i]);
            }
        }
    }
    dfs(b[1],-1);
    cout<<ans<<endl;
} 


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    t=1;
    cin>>t;
    while(t--){
        solve();
    }
    system("pause");
    return 0;
}

原文地址：https://blog.csdn.net/Unlimited_ci/article/details/140306807

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！