Pagini recente » Cod sursa (job #862196) | Cod sursa (job #1053342) | Cod sursa (job #2065202) | Cod sursa (job #2322666) | Cod sursa (job #954819)
Cod sursa(job #954819)
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
const size_t MAXN = 100010;
int idx = 1;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
void DFS (int v, int parent,
vector <int> &dfsIdx, vector <int> &lowIdx,
vector <int> (&G)[MAXN], stack <pair <int, int>> &edges,
vector <vector <int>> &BC)
{
dfsIdx[v] = lowIdx[v] = idx++;
for (auto &n : G[v])
if (n == parent) continue;
else if (dfsIdx[n] == 0)
{
edges.push (make_pair (v, n));
DFS (n, v, dfsIdx, lowIdx, G, edges, BC);
lowIdx[v] = min (lowIdx[v], lowIdx[n]);
if (lowIdx[n] >= dfsIdx[v])
{
int x, y;
BC.push_back (vector <int>());
do {
x = edges.top().first;
y = edges.top().second;
edges.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 N, m;
vector <int> G[MAXN];
vector <vector <int>> BC;
for (fin >> N >> m; m; --m)
{
int x, y;
fin >> x >> y;
G[x].push_back (y);
G[y].push_back (x);
}
vector <int> dfsIdx (N+1, 0), lowIdx (N+1);
stack <pair <int, int>> edges;
for (int v = 1; v <= N; ++v)
if (!dfsIdx[v])
{
DFS (v, 0, dfsIdx, lowIdx, G, edges, BC);
}
fout << BC.size() << '\n';
for (auto &bc : BC)
{
for (auto &v : bc)
fout << v << ' ';
fout << '\n';
}
return EXIT_SUCCESS;
}