Pagini recente » Cod sursa (job #2754960) | Cod sursa (job #860482) | Cod sursa (job #1458558) | Cod sursa (job #2271855) | Cod sursa (job #2396587)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
int n,m,nr;
vector<int>g[100003];
stack<int>s;
vector<int>sol[100003];
int niv[100003],llk[100003];
void citire()
{
ifstream fin("biconex.in");
fin>>n>>m;
int x,y;
for(int i=0;i<m;i++)
{
fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
}
void dfs(int vf,int tata)
{
niv[vf]=niv[tata]+1;
s.push(vf);
llk[vf]=niv[vf];
for(auto &fiu:g[vf])
{
if(fiu==tata)
continue;
if(niv[fiu])
{
llk[vf]=llk[vf]<niv[fiu]?llk[vf]:niv[fiu];
continue;
}
dfs(fiu,vf);
llk[vf]=llk[vf]<llk[fiu]?llk[vf]:llk[fiu];
if(niv[vf]<=llk[fiu])
{
int x;
nr++;
do
{
x=s.top();
sol[nr].push_back(x);
s.pop();
}while(!s.empty()&&x!=fiu);
sol[nr].push_back(vf);
}
}
}
void afisare()
{
ofstream fout("biconex.out");
fout<<nr<<"\n";
for(int i=1;i<=nr;i++)
{
for(auto &j:sol[i])
fout<<j<<" ";
fout<<"\n";
}
}
int main()
{
citire();
dfs(1,0);
afisare();
return 0;
}