Cod sursa(job #2648304)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 9 septembrie 2020 22:24:44
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.47 kb
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;

const long double PI = acos(-1);
const long long MOD = 1000000000 +7;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;

ll gcd(ll a, ll b){ return b==0?a:gcd(b,a%b);}

ll add(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a+b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll mul(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a*b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}

ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}

int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
	
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}

int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}

/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/

const int N = 300000 + 5;

int n;
int m;
int T;
int len;
vi G[N];
vi E[N];
int vis[N];
int low[N];
int tin[N];
vector<ii> cur;
vector<int> comp[N];
bool articulation[N];

void DFS(int u, int p = -1){
	int children = 0;
	vis[u] = 1;
	tin[u] = low[u] = T++;
	for(int v : G[u]){
		if(v == p or vis[v] == 2) continue;
		if(vis[v]){
			low[u] = min(low[u], tin[v]);
			if(tin[v] < tin[u]) cur.emplace_back(mp(u, v));
		}
		else{
			cur.emplace_back(mp(u, v));
			DFS(v, u);
			low[u] = min(low[u], low[v]);
			if((p == -1 and children > 1) or low[v] >= tin[u]){
				set<int> S;
				while(cur.back() != mp(u, v)){
					S.emplace(cur.back().first);
					S.emplace(cur.back().second);
					cur.pop_back();
				}
				S.emplace(cur.back().first);
				S.emplace(cur.back().second);
				cur.pop_back();
				for(auto x : S){
					comp[len].emplace_back(x);
				}
				len += 1;
			}
		}
	}
	vis[u] = 2;
}

int main(){
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	ri2(n, m);
	for(int i = 0; i < m; i++){
		int u, v;
		ri2(u, v);
		G[u].emplace_back(v);
		G[v].emplace_back(u);
		E[u].emplace_back(v);
		E[v].emplace_back(u);
	}
	DFS(1);
	printf("%d\n", len);
	for(int i = 0; i < len; i++){
		for(int j = 0; j < comp[i].size(); j++){
			printf("%d%c", comp[i][j], " \n"[j + 1 == comp[i].size()]);
		}
	}
	return 0;
}