Pagini recente » Cod sursa (job #1593926) | Cod sursa (job #289838) | Cod sursa (job #1944005) | Cod sursa (job #1295661) | Cod sursa (job #1728281)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,i,j,x,y,viz[100001],H[100001];
vector <int> G[100001],comp;
vector <vector <int>> bic;
stack <int> St;
void dfs(int nod,int h)
{
int v,hh,i;
H[nod]=h;
viz[nod]=1;
St.push(nod);
hh=h;
for (i=0;i<G[nod].size();i++)
{
v=G[nod][i];
if(viz[v]) hh=min(hh,H[v]);
else
{
dfs(v,h+1);
hh=min(hh,H[v]);
if(H[v]==h)
{
comp.clear();
while(St.top()!=v)
{
comp.push_back(St.top());
St.pop();
}
comp.push_back(St.top());
St.pop();
comp.push_back(nod);
bic.push_back(comp);
}
}
}
H[nod]=hh;
}
int main()
{
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(i=1;i<=n;i++)
if(viz[i]==0)
dfs(i,0);
g<<bic.size()<<'\n';
for(i=0;i<bic.size();i++)
{
for(j=0;j<bic[i].size();j++) g<<bic[i][j]<<' ';
g<<'\n';
}
return 0;
}