Submission #2326127

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int INF=1001001001001001001ll;

vector<int> G[1000000];
vector<pair<int, int> > bridge;
vector<int> articulation;
int ord[1000000], low[1000000];
bool vis[1000000];

void dfs(int v, int p, int &k)
{
	vis[v] = true;

	ord[v] = k++;
	low[v] = ord[v];

	bool isArticulation = false;
	int ct = 0;

	for (int i = 0; i < G[v].size(); i++){
		if (!vis[G[v][i]]){
			ct++;
			dfs(G[v][i], v, k);
			low[v] = min(low[v], low[G[v][i]]);
			if (~p && ord[v] <= low[G[v][i]]) isArticulation = true;
			if (ord[v] < low[G[v][i]]) bridge.push_back(make_pair(min(v, G[v][i]), max(v, G[v][i])));
		}
		else if (G[v][i] != p){
			low[v] = min(low[v], ord[G[v][i]]);
		}
	}

	if (p == -1 && ct > 1) isArticulation = true;
	if (isArticulation) articulation.push_back(v);
}


struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

vint T[222222];

int N,M;
int A[222222],B[222222];

int cnt;
int latte[222222];
int malta[222222];
int ans;

void dfs2(int v,int p){
    if(T[v].size()==1)latte[v]=1;
    malta[v]=1;
    for(auto u:T[v]){
        if(u==p)continue;
        dfs2(u,v);
        latte[v]+=latte[u];
        malta[v]+=malta[u];
    }

    if(p!=-1){
        int tmp=0;
        int sz=latte[v];
        if(T[v].size()==2)sz++;
        if(sz!=1)tmp+=(sz+1)/2;


        sz=cnt-latte[v];
        if(T[p].size()==2)sz++;

        if(sz!=1)tmp+=(sz+1)/2;
        if(malta[v]==2||N-malta[v]==2)tmp=INF;
        chmin(ans,tmp);
    }
}

signed main(){
    cin>>N>>M;
    rep(i,M){
        int a,b;
        cin>>a>>b;
        G[a].pb(b);G[b].pb(a);
        A[i]=a;B[i]=b;
    }
    int K=0;
    dfs(0,-1,K);

    if(bridge.size()==0){
        cout<<"IMPOSSIBLE"<<endl;
        return 0;
    }

    sort(all(bridge));

    UnionFindTree uf(N);

    rep(i,M){
        if(A[i]>B[i])swap(A[i],B[i]);
        if(binary_search(all(bridge),pint(A[i],B[i])))continue;
        uf.unite(A[i],B[i]);
    }

    for(auto p:bridge){
        int u=uf.find(p.fi);
        int v=uf.find(p.se);
        cout<<u<<" "<<v<<endl;
        T[u].pb(v);T[v].pb(u);
    }
    rep(i,N)if(uf.find(i)==i&&T[i].size()==1)cnt++;

    ans=INF;
    dfs2(uf.find(0),-1);
    if(ans==INF)cout<<"IMPOSSIBLE"<<endl;
    else cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result