Cod sursa(job #2261149)

Utilizator MaarcellKurt Godel Maarcell Data 15 octombrie 2018 23:42:36
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <ctime>
#include <unordered_map>
#include <iomanip>
#include <complex>
#include <cassert>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define deb(a) cerr<< #a << "= " << (a)<<"\n";

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;
typedef complex<double> base;
typedef vector<int> vi;
typedef pair<int,int> pii;

template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream; }
ll fpow(ll x, ll p, ll m){ll r=1; for (;p;p>>=1){ if (p&1) r=r*x%m; x=x*x%m; } return r;}
ll inv(ll a, ll b){ return a<2 ? a : ((a-inv(b%a,a))*b+1)/a%b; }
int gcd(int a, int b){ if (!b) return a; return gcd(b,a%b);}
ll gcd(ll a, ll b){ if (!b) return a; return gcd(b,a%b);}


int N,M;
vi g[100100]; int d[100100],md[100100];
bool v[100100]; vector<vi> comp;
vi stk;



void dfs(int nod, int cd, vi &arr){
	v[nod]=1;
	d[nod]=md[nod]=cd;
	arr.pb(nod);
	
	for (int nxt : g[nod])
		if (!v[nxt]){
			
			vi new_arr;
			
			dfs(nxt,cd+1,new_arr);
			
			if (md[nxt]>md[nod]){
				if (new_arr.size()>1) comp.pb(new_arr);
				comp.pb({nod,nxt});
			}
			
			else arr.insert(arr.end(),all(new_arr));
			md[nod]=min(md[nod],md[nxt]);
		}
		else if (d[nxt]<d[nod]-1) md[nod]=min(md[nod],d[nxt]);
		
	if (nod==1) comp.pb(arr);
}



int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	ifstream fin("biconex.in");
	ofstream fout("biconex.out");	
	fin >> N >> M;

	int i;
	for (i=1; i<=M; i++){
		int x,y;
		fin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	
	vi aux;
	dfs(1,0,aux);
	

	
	
	cout << comp.size() << "\n";
	
	for (auto c : comp){
		sort(all(c));
		for (int x : c)
			cout << x << " ";
			
		cout << "\n";
	}
	return 0;
}