Cod sursa(job #1932758)

Utilizator valentin50517Vozian Valentin valentin50517 Data 20 martie 2017 08:35:54
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>
#define maxn 1<<17
#define pb push_back
using namespace std;
vector<int> V[maxn],RS[maxn];
int N,M,T[maxn],P[maxn],rs,St[maxn],st;
void dfs(int x){
	St[++st] = x;
	for(auto y:V[x]) if(P[y]) P[x] = min(P[x],T[y]);
	else{
		int p=st;
		P[y] = T[y] = T[x] + 1;
		dfs(y);
		P[x] = min(P[x],P[y]);
		if(P[y] >= T[x]){
			RS[++rs].pb(x);
			while(p<st) RS[rs].pb(St[st--]);
		}
	}
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    ifstream cin("biconex.in");
	ofstream cout("biconex.out");
    cin >> N >> M;
    for(int x,y;M--;){
		cin >> x >> y;
		V[x].pb(y); V[y].pb(x);
	}
	T[1] = P[1] = 1;
	dfs(1);
	cout << rs << '\n';
	while(rs){
		for(auto it:RS[rs]) cout << it << ' ';
		cout << '\n'; rs--;
	}
}