Pagini recente » Cod sursa (job #3304583) | Cod sursa (job #3306173) | Cod sursa (job #3315341) | Cod sursa (job #3342383) | Cod sursa (job #3306987)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int NMAX = 100001;
vector<vector<int>> compBiconexe;
vector<int> G[NMAX];
int level[NMAX], lmin[NMAX];
void DFS(int root, int parent, vector<int> &S)
{
level[root] = level[parent] + 1;
lmin[root] = level[root];
S.push_back(root);
for (auto x: G[root])
{
if (x == parent)
{
continue;
}
if (level[x] == 0)
{
DFS(x, root, S);
if (lmin[x] >= level[root])
{
vector<int> crtCompBicon;
while (S.back() != root)
{
crtCompBicon.push_back(S.back());
S.pop_back();
}
crtCompBicon.push_back(root);
compBiconexe.push_back(crtCompBicon);
}
lmin[root] = min(lmin[root], lmin[x]);
}
else
{
lmin[root] = min(lmin[root], level[x]);
}
}
}
int main()
{
int n, m;
f >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
f >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> S;
DFS(1, 0, S);
g << compBiconexe.size() << '\n';
for (auto comp: compBiconexe)
{
for (auto node: comp)
{
g << node << ' ';
}
g << '\n';
}
return 0;
}