Pagini recente » Cod sursa (job #762210) | Cod sursa (job #1605662) | Cod sursa (job #2615248) | Cod sursa (job #156105) | Cod sursa (job #3288497)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax = 1e5 + 1;
int adancime[nmax], adancime_min[nmax], parent[nmax];
vector <int> edges[nmax], stack_muchii, aux;
vector <vector <int>> comp_biconexe;
void dfs( int vf, int parinte ) {
parent[vf] = parinte;
//cout << vf << "VF\n";
adancime[vf] = adancime[parinte] + 1;
for( int copil: edges[vf] ) {
if( copil == parinte )
continue;
if (adancime[copil] != 0)
continue;
stack_muchii.push_back(copil);
dfs( copil, vf );
if( adancime_min[copil] >= adancime[vf] ) {
//cout << copil << " " << vf << "\n";
aux.clear();
while( stack_muchii.back() != copil ) {
//cout << stack_muchii.back() << "aux ";
aux.push_back(stack_muchii.back());
stack_muchii.pop_back();
}
aux.push_back(copil);
if( !aux.empty() )
comp_biconexe.push_back(aux);
}
}
adancime_min[vf] = adancime[vf];
for( int copil: edges[vf] ) {
if (copil == parinte)
continue;
if( adancime_min[copil] == 0 )
adancime_min[vf] = min(adancime_min[vf], adancime[copil]);
else
adancime_min[vf] = min( adancime_min[vf], adancime_min[copil] );
}
//cout << vf << " " << adancime_min[vf] << "\n";
}
int main() {
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m;
cin >> n >> m;
for( int i = 1; i <= m; i++ ) {
int x, y;
cin >> x >> y;
edges[x].push_back(y);
edges[y].push_back(x);
}
dfs( 1, 0 );
cout << comp_biconexe.size() << "\n";
for( vector <int> x: comp_biconexe ) {
vector <int> y = x;
for( int i = 0; i < x.size(); i++ )
y.push_back(parent[x[i]]);
sort( y.begin(), y.end() );
cout << y[0] << " ";
for( int i = 1; i < y.size(); i++ )
if( y[i] != y[i - 1] )
cout << y[i] << " ";
cout << "\n";
}
}