Pagini recente » Cod sursa (job #2879972) | Cod sursa (job #880011) | Cod sursa (job #819674) | Cod sursa (job #1018005) | Cod sursa (job #648008)
Cod sursa(job #648008)
#include<fstream>
#include<vector>
using namespace std;
#define NMAX 100003
int n , m;
int nivelul_min[NMAX], nivelul_dfs[NMAX], viz[NMAX];
int stiva_tata[NMAX] , stiva_fiu[NMAX];
vector lista[NMAX];
vector comp[NMAX];
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(int i = 0 ; i< lista[nod].end(); i++)
if(viz[lista[nod][i]]==1)
nivelul_min[nod] = min( nivelul_min[nod], nivelul_bfs[lista[nod][i]]);
else{
nivelul_bfs[lista[nod][i]] = nivelul_bfs[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].end();i++){
fout<<comp[k][i]<<" ";
}
fout<<endl;
}
return 0;
}