Pagini recente » Cod sursa (job #262514) | Cod sursa (job #133715) | Cod sursa (job #706594) | Cod sursa (job #3130068) | Cod sursa (job #2096491)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int N = 100002;
int dep[N], lowest[N], st[N][2], stSize, nrBiComp;
bool viz[N];
vector <int> v[N], comp[N];
void newBiComp(int ns, int nbr){
nrBiComp++;
while(!(st[stSize][0] == ns && st[stSize][1] == nbr))
comp[nrBiComp].push_back(st[stSize--][1]);
stSize--;
comp[nrBiComp].push_back(ns);
comp[nrBiComp].push_back(nbr);
}
void DFS(int ns){
int sz = v[ns].size(), nbr;
viz[ns] = true;
lowest[ns] = dep[ns];
for(int i=0;i<sz;i++){
nbr = v[ns][i];
if(viz[nbr] == false){
dep[nbr] = dep[ns] + 1;
st[++stSize][0] = ns;
st[stSize][1] = nbr;
DFS(nbr);
if(lowest[nbr] >= dep[ns])
newBiComp(ns,nbr);
if(lowest[ns] > lowest[nbr])
lowest[ns] = lowest[nbr];
}
else if(lowest[ns] > dep[nbr])
lowest[ns] = dep[nbr];
}
}
int main()
{
int n,m,x,y,sz;
in>>n>>m;
for(int i=1;i<=m;i++){
in>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
in.close();
DFS(1);
out<<nrBiComp<<"\n";
for(int i=1;i<=nrBiComp;i++){
sz = comp[i].size();
for(int j=0;j<sz;j++)
out<<comp[i][j]<<" ";
out<<"\n";
}
out.close();
return 0;
}