Pagini recente » Cod sursa (job #993474) | Cod sursa (job #1712041) | Cod sursa (job #2257683) | Cod sursa (job #2321294) | Cod sursa (job #2715323)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> v[100010];
vector <pair<int,int>> c;
vector <vector<int>> b;
stack<int> st;
int n,m,nrbi;
bool critical[100010],viz[100010];
int niv[100010], nmin[100010];
void dfs(int nod, int tata, int rad)
{
int aux,cnt=0;
viz[nod]=1;
niv[nod]=nmin[nod]=niv[tata]+1;
st.push(nod);
for (vector<int>::iterator i=v[nod].begin();i!=v[nod].end();i++)
{
if (*i!=tata)
{
if (viz[*i])
{
if (nmin[nod]>niv[*i])
nmin[nod]=niv[*i];
}
else
{
cnt++;
dfs(*i,nod,rad);
if (nmin[nod]>nmin[*i])
nmin[nod]=nmin[*i];
if (niv[nod]<nmin[*i])
c.push_back((make_pair(nod,*i)));
if (niv[nod]<=nmin[*i])
{
nrbi++;
b.push_back(vector<int>(0));
do
{
aux=st.top();
st.pop();
b[nrbi-1].push_back(aux);
} while(aux!=*i);
b[nrbi-1].push_back(nod);
if (nod!=rad)
critical[nod]=1;
}
}
}
}
if (nod==rad && cnt>1)
critical[nod]=1;
}
int main()
{
int i,j,x,y,cnt=0;
fin>>n>>m;
for (i=1;i<=m;i++)
{
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for (i=1;i<=n;i++)
if (viz[i]==0)
dfs(i, 0, i);
fout<<nrbi<<'\n';
for (i=0;i<nrbi;i++)
{
///fout<<b[i].size()<<" ";
for (j=0;j<b[i].size();j++)
fout<<b[i][j]<<" ";
fout<<'\n';
}
return 0;
}