Pagini recente » Profil elizanatalia50 | Cod sursa (job #1049664) | Cod sursa (job #998932) | Profil Rares_99 | Cod sursa (job #955027)
Cod sursa(job #955027)
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
const size_t MAXN = 100010;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
int N, idx, dfsIdx[MAXN], lowIdx[MAXN];
vector <int> G[MAXN];
vector <vector <int>> bc;
stack <pair <int, int>> eSt;
void DFS (int v, int parent)
{
dfsIdx[v] = lowIdx[v] = ++idx;
for (auto &n : G[v])
if (n == parent) continue;
else if (!dfsIdx[n])
{
eSt.push (make_pair (v, n));
DFS (n, v);
lowIdx[v] = min (lowIdx[v], lowIdx[n]);
if (lowIdx[n] >= dfsIdx[v])
{
int x, y;
bc.push_back (vector <int>());
do {
x = eSt.top().first;
y = eSt.top().second;
eSt.pop();
bc.back().push_back (y);
} while (x != v && y != n);
bc.back().push_back (v);
}
}
else lowIdx[v] = min (lowIdx[v], lowIdx[n]);
}
int main()
{
int m, x, y;
for (fin >> N >> m; m; --m)
{
fin >> x >> y;
G[x].push_back (y);
G[y].push_back (x);
}
for (size_t v = 1; v <= N; ++v)
if (!dfsIdx[v])
DFS (v, 0);
fout << bc.size() << '\n';
for (auto &biconex : bc)
{
for (auto &v : biconex)
fout << v << ' ';
fout << '\n';
}
return EXIT_SUCCESS;
}