Submission #3108539

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

class biconnected{
public:
	using P = pair<int, int>;
	int V,kind;
	vector<vector<int> > G,tree;
	vector<vector<P> > check;
	vector<int> ord,low,cmp;
	vector<P> bridge;
	vector<bool> visit;
	biconnected(int node_size) : V(node_size), kind(0), G(V), check(V), ord(V), low(V)
									,cmp(V), visit(V, false){}
	void build(){
		int id = 0;
		rep(i,V){
			if(!visit[i]){
				dfs(i,-1,id);
			}
		}
	}
	void dfs(int v,int p,int &k)
	{
		visit[v] = true;
		ord[v] = k++;
		low[v] = ord[v];
		rep(i,(int)G[v].size()){
			int w = G[v][i];
			if(!visit[w]){
				dfs(w,v,k);
				low[v] = min(low[v],low[w]);
				if(ord[v] < low[w]){
				    bridge.push_back(P(v,w));
	                check[v][i].second = 1;
	                check[w][check[v][i].first].second = 1;
				}
			//(v,w)は後退辺
			}else if(w != p){
				low[v] = min(low[v],ord[w]);
			}
		}
	}

	void add_edge(int u,int v)
	{
	    G[u].push_back(v),G[v].push_back(u);
	    check[u].push_back(P((int)check[v].size(),0));
	    check[v].push_back(P((int)check[u].size()-1,0));
	}
	void restrict_dfs(int u,int p,int kind,queue<int>& que)
	{
	    visit[u] = true;
	    cmp[u] = kind;
	    rep(i,(int)G[u].size()){
			int w = G[u][i];
	        if(check[u][i].second){
	            if(!visit[w]){
	                que.push(w);
	            }
	        }else if(!visit[w]){
	            restrict_dfs(w,u,kind,que);
	        }
	    }
	}
    void rebuild()
    {
	    fill(visit.begin(),visit.end(),false);
	    rep(i,V){
	        if(!visit[i]){
	            queue<int> que;
	            que.push(i);
	            while(!que.empty()){
	                int p = que.front();
	                que.pop();
	                restrict_dfs(p,-1,kind,que);
	                kind++;
	            }
	        }
	    }
    }
	// auxiliary graph を作る
	void make_bctree()
	{
		tree.resize(V);
		rebuild();
	    rep(i,(int)bridge.size()){
	        int a = cmp[bridge[i].first];
	        int b = cmp[bridge[i].second];
	        tree[a].push_back(b), tree[b].push_back(a);
	    }
	}
};
int main(){
    int n,m;
    cin >> n >> m;
    biconnected bc(n);
    rep(i,m){
        int a,b;
        cin >> a >> b;
        bc.add_edge(a,b);
    }
    bc.build();
    bc.make_bctree();
    if(bc.bridge.size()==0||n==3||n==1){
        cout <<"IMPOSSIBLE" << endl;
    }else if(bc.bridge.size()==1){
        cout << 0 << endl;
    }else{
        int s = bc.kind;
        vector<vector<int> > p = bc.tree;
        bool flag = 0;
        int ans = 0;
        for(int i=0;i<s;i++){
            if(p[i].size()==1){
                ans++;
                if(p[p[i][0]].size()!=2){
                    flag = 1;
                }
            }
        }
        if(ans%2==0){
            cout << ans/2 << endl;
        }else{
            if(flag){
                cout << ans/2 << endl;
            }else{
                cout << ans/2+1 << endl;
            }
        }
    }
    return 0;
}

Submission Info

Judge Result