Cod sursa(job #2648307)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 9 septembrie 2020 22:41:28
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.92 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];
int low[N];
int tin[N];
int comp[N];
bool vis[N];
bool used[N];
vector<ii> cur;

void DFS(int u, int p = -1){
	vis[u] = 1;
	int children = 0;
	tin[u] = low[u] = T++;
	for(int v : G[u]){
		if(v == p) continue;
		if(vis[v]){
			low[u] = min(low[u], tin[v]);
		}
		else{
			DFS(v, u);
			low[u] = min(low[u], low[v]);
			if(low[v] >= tin[u] or (p == -1 and children > 1)){
				len += 1;
			}
			children += 1;
		}
	}
}

void DFS2(int u, int p = -1){
	vis[u] = 1;
	int children = 0;
	tin[u] = low[u] = T++;
	for(int v : G[u]){
		if(v == p) continue;
		if(vis[v]){
			low[u] = min(low[u], tin[v]);
			if(tin[v] < tin[u]) cur.emplace_back(mp(u, v));
		}
		else{
			children += 1;
			cur.emplace_back(mp(u, v));
			DFS2(v, u);
			low[u] = min(low[u], low[v]);
			if((p == -1 and children > 1) or low[v] >= tin[u]){
				len = 0;
				while(cur.back() != mp(u, v)){
					int x = cur.back().first;
					int y = cur.back().second;
					if(not used[x]){
						used[x] = true;
						comp[len++] = x;
					}
					if(not used[y]){
						used[y] = true;
						comp[len++] = y;
					}
					cur.pop_back();
				}
				if(not used[u]){
					used[u] = true;
					comp[len++] = u;
				}
				if(not used[v]){
					used[v] = true;
					comp[len++] = v;
				}
				cur.pop_back();
				for(int i = 0; i < len; i++){
					printf("%d%c", comp[i], " \n"[i + 1 == len]);
					used[comp[i]] = false;
				}
			}
		}

	}
}

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);
	}
	DFS(1);
	printf("%d\n", len);
	for(int i = 1; i <= n; i++) vis[i] = 0;
	T = 0;
	DFS2(1);
	return 0;
}