Submission #3272323

---

Source Code Expand

#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;


//無向
class Bridge{
private:
    typedef vector<vector<ll>> edge;
    edge E;
    ll v;
    vector<pll> count;
    
    ll dfs(ll w,ll depth,ll parent){
        if(count[w].F!=-1){return 1e18;}
        count[w]={depth,depth};
        bool p=true;
        for(int i=0;i<E[w].size();i++){
            if(E[w][i]==parent){
                if(!p){count[w].S=min(count[E[w][i]].F,count[w].S);}
                p=false;
            }
            else if(count[E[w][i]].F==-1){count[w].S=min(dfs(E[w][i],depth+1,w),count[w].S);}
            else{count[w].S=min(count[E[w][i]].F,count[w].S);}
        }
        return count[w].S;
    }
    
public:
    Bridge(ll v,edge e={}):v(v),E(e),count(v,{-1,-1}){
        E.resize(v);
    }
    
    void add_edge(ll from,ll to){
        E[from].push_back(to);
        E[to].push_back(from);
    }
    
    void search(){
        dfs(0,1,-1);
    }
    
    bool is_bridge(ll u,ll v){
        if(count[u].F==count[v].F){return false;}
        if(count[u].F>count[v].F){swap(u,v);}
        if(count[u].F>=count[v].S){return false;}
        return true;
    }
    
    vector<pll> bridge(){
        vector<pll> ret;
        for(int i=0;i<v;i++){
            for(int t=0;t<E[i].size();t++){
                if(i<E[i][t] && is_bridge(i,E[i][t])){ret.push_back({i,E[i][t]});}
            }
        }
        return ret;
    }
    
    void test(){
        for(int i=0;i<v;i++){
            cout<<"test "<<i<<" "<<count[i].F<<" "<<count[i].S<<endl;
        }
    }
};



int main(){
    ll v,e;
    cin>>v>>e;
    Bridge B(v);
    for(int i=0;i<e;i++){
        ll s,t;
        cin>>s>>t;
        B.add_edge(s,t);
    }
    B.search();
    vector<pll> b=B.bridge();
    if(b.size()>1){cout<<"IMPOSSIBLE"<<endl;}
    else{cout<<1-b.size()<<endl;}
    
    
    return 0;
}

Submission Info

Judge Result