Pagini recente » Cod sursa (job #2862116) | Cod sursa (job #2133793) | Cod sursa (job #3271953) | Cod sursa (job #16586) | Cod sursa (job #3192682)
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
int x, y;
vector<int> l[NMAX];
int in[NMAX], low[NMAX];
int counter;
int nrcc;
vector<int> cc[NMAX];
stack<int> s;
int i, j;
void dfs(int, int);
int main()
{
fin >>n>>m;
for (i = 1; i <= m; ++i)
{
fin >>x>>y;
l[x].push_back(y);
l[y].push_back(x);
}
dfs(1, -1);
fout <<nrcc<<'\n';
for (i = 1; i <= nrcc; ++i)
{
for (auto vf: cc[i])
fout <<vf<<' ';
fout <<'\n';
}
fout.close();
return 0;
}
void dfs(int vf, int tata)
{
in[vf] = low[vf] = ++counter;
s.push(vf);
for (auto vfnou: l[vf])
{
if (vfnou == tata) continue;
if (!in[vfnou])
{
dfs(vfnou, vf);
low[vf] = min(low[vf], low[vfnou]);
if (low[vfnou] >= in[vf])
{
nrcc++;
int fiu;
do
{
fiu = s.top();
cc[nrcc].push_back(fiu);
s.pop();
}
while (fiu != vfnou);
cc[nrcc].push_back(vf);
}
}
else
low[vf] = min(low[vf], in[vfnou]);
}
}