Pagini recente » Cod sursa (job #980753) | Cod sursa (job #980086) | Profil girl_006_007 | Cod sursa (job #1678687) | Cod sursa (job #648028)
Cod sursa(job #648028)
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
vector <int> lista[100003];
vector <int> comp[100003];
int n , m;
int nivelul_min[100003], nivelul_dfs[100003], viz[100003], stiva_tata[100003] , stiva_fiu[100003];
int vf;
int k;
inline int min( int a, int b ){
if(a>b) return b;
return a;
}
void dfs(int nod){
viz[nod]=1;
nivelul_min[nod]=nivelul_dfs[nod];
for( unsigned int i = 0 ; i< lista[nod].size(); i++)
if(viz[lista[nod][i]]==1)
nivelul_min[nod] = min( nivelul_min[nod], nivelul_dfs[lista[nod][i]]);
else{
nivelul_dfs[lista[nod][i]] = nivelul_dfs[nod]+1;
vf++;
stiva_tata[vf]=nod;
stiva_fiu[vf]=lista[nod][i];
dfs(stiva_fiu[vf]);
if(nivelul_min[lista[nod][i]] >= nivelul_dfs[nod]){ //comp
k++;
while( stiva_tata[vf]!=nod || stiva_fiu[vf]!=lista[nod][i]){
comp[k].push_back(stiva_fiu[vf]);
vf--;
}
comp[k].push_back(stiva_tata[vf]);
comp[k].push_back(stiva_fiu[vf]);
vf--;
}
nivelul_min[nod] = min ( nivelul_min[nod], nivelul_min[lista[nod][i]] );
}
}
int main(){
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
fin>>x>>y;
lista[x].push_back(y);
lista[y].push_back(x);
}
dfs(1);
fout<<k<<endl;
for(int j=1;j<=k;j++){
for(int i=0;i<comp[k].size();i++){
fout<<comp[k][i]<<" ";
}
fout<<endl;
}
return 0;
}