Pagini recente » Cod sursa (job #605744) | Cod sursa (job #2085709) | Istoria paginii runda/preojiiiiii/clasament | Istoria paginii runda/caracatita_paul/clasament | Cod sursa (job #2574192)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N,M,nrC;
int Niv[100005],NivMin[100005];
bool Viz[100005];
vector<int>Ad[100005],Comp[100005];
stack<int>S;
void citire()
{
int x,y;
fin>>N>>M;
for(int i=1;i<=M;i++)
{
fin>>x>>y;
Ad[x].push_back(y);
Ad[y].push_back(x);
}
}
void compBicon(int vf)
{
nrC++;
while(S.top()!=vf)
{
Comp[nrC].push_back(S.top());
S.pop();
}
S.pop();
}
void DFS(int vf,int tata)
{
Niv[vf]=NivMin[vf]=Niv[tata]+1;
Viz[vf]=1;
S.push(vf);
for(unsigned i=0;i<Ad[vf].size();i++)
{
if(Viz[Ad[vf][i]])
NivMin[vf]=min(NivMin[vf],Niv[Ad[vf][i]]);
else
{
DFS(Ad[vf][i],vf);
NivMin[vf]=min(NivMin[vf],NivMin[Ad[vf][i]]);
if(NivMin[Ad[vf][i]]>=Niv[vf])
{
compBicon(Ad[vf][i]);
Comp[nrC].push_back(vf);
Comp[nrC].push_back(Ad[vf][i]);
}
}
}
}
void afisare()
{
fout<<nrC<<'\n';
for(int i=1;i<=nrC;i++)
{
for(unsigned j=0;j<Comp[i].size();j++)
fout<<Comp[i][j]<<" ";
fout<<'\n';
}
}
int main()
{
citire();
DFS(1,0);
afisare();
return 0;
}