Pagini recente » Cod sursa (job #143943) | Cod sursa (job #2363725) | Cod sursa (job #562433) | Cod sursa (job #571948) | Cod sursa (job #1135396)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
int nr=0, niv1[100000], niv2[100000];
vector<int> a[100000], componente[100000];
stack < pair <int,int> > stiva;
void DFS(int vf, int tata, int niv)
{
int i, vecin, x, y;
niv1[vf]=niv;
niv2[vf]=niv;
for(i=0;i<a[vf].size();i++)
{
vecin=a[vf][i];
if(tata==vecin)
continue;
if(niv1[vecin]==-1)
{
stiva.push(make_pair(vf, vecin));
DFS(vecin, vf, niv+1);
niv2[vf]=min(niv2[vf], niv2[vecin]);
if(niv1[vf]<=niv2[vecin])
{
do
{
x=stiva.top().first;
y=stiva.top().second;
stiva.pop();
componente[nr].push_back(y+1);
} while(x!=vf && y!=vecin);
componente[nr].push_back(x+1);
nr++;
}
}
else
niv2[vf]=min(niv2[vf], niv1[vecin]);
}
}
int main()
{
int i, x, y, m, n, j;
ifstream f("biconex.in");
ofstream g("biconex.out");
f>>n>>m;
for(i=0;i<m;i++)
{
f>>x>>y;
a[x-1].push_back(y-1);
a[y-1].push_back(x-1);
}
for(i=0; i<n; i++)
niv1[i]=-1;
for(i=0;i<n;i++)
DFS(i,0,0);
g<<nr<<"\n";
for(i=0;i<nr;i++)
{
for(j=0;j<componente[i].size();j++)
g<<componente[i][j]<<" ";
g<<"\n";
}
}