Pagini recente » Cod sursa (job #1512371) | Cod sursa (job #2080362) | Cod sursa (job #2846462) | Cod sursa (job #1044417) | Cod sursa (job #3216942)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
#define NMAX 100008
int n,i,j,nrcomp,m,a,b;
int depth[NMAX],l[NMAX];
bool viz[NMAX];
vector<int>muchii[NMAX],comp[NMAX];
stack<int>stiva;
void input ();
void dfs(int node, int parent);
int main()
{
input();
dfs(1,0);
fout<<nrcomp<<'\n';
for (i=1; i<=nrcomp; i++)
{
for (auto it : comp[i])
{
fout<<it<<' ';
}
fout<<'\n';
}
return 0;
}
void input ()
{
fin>>n>>m;
for (i=1; i<=m; i++)
{
fin>>a>>b;
muchii[b].push_back(a),muchii[a].push_back(b);
}
}
void dfs(int node, int parent)
{
viz[node]=1;
depth[node]=l[node]=depth[parent]+1;
stiva.push(node);
for (auto vec : muchii[node])
{
if (vec!=parent)
{
if (viz[vec])
{
l[node]=min(l[node],depth[vec]);
}
else
{
dfs(vec,node);
l[node]=min(l[node],l[vec]);
if (l[vec]>=depth[node])
{
nrcomp++;
while (stiva.top()!=vec)
{
comp[nrcomp].push_back(stiva.top());
stiva.pop();
}
comp[nrcomp].push_back(vec);
stiva.pop();
comp[nrcomp].push_back(node);
}
}
}
}
}