Mai intai trebuie sa te autentifici.
Cod sursa(job #1541531)
Utilizator | Data | 4 decembrie 2015 10:41:23 | |
---|---|---|---|
Problema | Componente biconexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.7 kb |
#include<fstream>
#include<deque>
#include<vector>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int nivel[100005],Low[100005],f[100005],componente,n,m,x,y;
deque< pair<int,int> > d;
vector<int> v[100005],sol[100005];
void dfs( int nod, int niv, int tata){
nivel[nod] = niv;
Low[nod] = niv;
f[nod] = 1;
for( int i = 0; i < v[nod].size(); i++ ){
int vecin = v[nod][i];
if( tata == vecin )
continue;
if( f[vecin] == 0 ){
d.push_back( make_pair( nod, vecin ) );
dfs( vecin, niv + 1, nod );
Low[nod] = min ( Low[nod], Low[vecin] );
if( nivel[nod] <= Low[vecin] ){
componente++;
int nod1 = d.back().first;
int nod2 = d.back().second;
while( nod1 != nod && nod2 != vecin && !d.empty() ){
sol[componente].push_back(nod2);
d.pop_back();
nod1 = d.back().first;
nod2 = d.back().second;
}
sol[componente].push_back(nod2);
sol[componente].push_back(nod1);
d.pop_back();
}
}else{
Low[nod] = min( Low[nod], nivel[vecin] );
}
}
}
int main(){
cin >> n >> m;
for( int i = 1; i <= m; i++ ){
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,1,0);
cout << componente << "\n";
for( int i = 1; i <= componente; i ++ ){
for( int j = 0; j < sol[i].size(); j ++ ){
cout << sol[i][j] << " ";
}
cout << "\n";
}
return 0;
}