Pagini recente » Cod sursa (job #2979489) | Cod sursa (job #3284724) | Cod sursa (job #411) | Cod sursa (job #1451712) | Cod sursa (job #3288472)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax = 1e5 + 1;
int adancime[nmax], adancime_min[nmax];
vector <int> edges[nmax], stack_muchii, aux;
vector <vector <int>> comp_biconexe;
void dfs( int vf, int parinte ) {
stack_muchii.push_back(vf);
//cout << vf << "VF\n";
adancime[vf] = adancime[parinte] + 1;
adancime_min[vf] = adancime[vf];
for( int copil: edges[vf] ) {
if( copil == parinte )
continue;
if (adancime[copil] != 0)
continue;
dfs( copil, vf );
adancime_min[vf] = min( adancime_min[vf], adancime_min[copil] );
if( adancime_min[vf] == adancime[vf] ) {
aux.clear();
while( stack_muchii.back() != vf ) {
//cout << stack_muchii.back() << "aux ";
aux.push_back(stack_muchii.back());
stack_muchii.pop_back();
}
if( !aux.empty() )
comp_biconexe.push_back(aux);
}
}
for( int copil: edges[vf] ) {
if (copil == parinte)
continue;
if (adancime[copil] != 0)
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 ) {
for( int y: x )
cout << y << " ";
cout << "\n";
}*/
}