Pagini recente » Diferente pentru implica-te/arhiva-educationala intre reviziile 8 si 9 | Monitorul de evaluare | Cod sursa (job #176871) | redsnow_1 | Cod sursa (job #2013014)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stack>
#include <queue>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> Q[100001];
vector<int> Z1,Z2;
stack<int>Z3;
vector< stack < int > >QQ;
int n,m,nrcomp;
void afisare(int limita)
{
stack<int>Z4;
int cnod;
do
{
cnod=Z3.top();
Z4.push(cnod);
Z3.pop();
}
while(cnod!=limita);
Z3.push(limita);
QQ.push_back(Z4);
++nrcomp;
}
void dfs(int nod,int tata,int numar)
{
Z1[nod]=Z2[nod]=numar;
for (vector<int>::iterator it=Q[nod].begin(); it!=Q[nod].end(); ++it)
{
if (*it==tata)continue;
if (Z1[*it]==-1)
{
Z3.push(*it);
dfs(*it,nod,numar+1);
Z2[nod]=min(Z2[nod],Z2[*it]);
if (Z2[*it]>=Z1[nod])
afisare(nod);
}
else
Z2[nod]=min(Z2[nod],Z1[*it]);
}
}
void citire()
{
int a,b;
f>>n>>m;
while (f>>a>>b)
{
Q[b].push_back(a);
Q[a].push_back(b);
}
}
int main()
{
citire();
Z1.resize(n+1);
Z1.assign(n+1,-1);
Z2.resize(n+1);
Z3.push(1);
dfs(1,0,0);
g<<nrcomp<<'\n';
for (int c=0;c<nrcomp;++c)
{
while (!QQ[c].empty())
g<<QQ[c].top()<<' ',QQ[c].pop();
g<<'\n';
}
return 0;
}