Pagini recente » Cod sursa (job #1310311) | Cod sursa (job #2400290) | Cod sursa (job #1147274) | Cod sursa (job #1158682) | Cod sursa (job #968565)
Cod sursa(job #968565)
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
int DFSINDEX = 1;
stack <pair <size_t, size_t>> edges;
void dfs (size_t v, size_t parent,
vector <size_t> &dfsReach, vector <size_t> &dfsIndex,
vector <vector <size_t>> &G, vector <vector <size_t>> &C)
{
dfsIndex[v] = dfsReach[v] = DFSINDEX++;
for (auto &n : G[v])
if (n == parent) continue;
else if (dfsIndex[n] == 0)
{
edges.push (make_pair (v, n));
dfs (n, v, dfsReach, dfsIndex, G, C);
if (dfsReach[v] > dfsReach[n])
dfsReach[v] = dfsReach[n];
if (dfsReach[n] >= dfsIndex[v])
{
C.push_back(vector <size_t>());
int x, y;
do {
x = edges.top().first;
y = edges.top().second;
edges.pop();
C.back().push_back (y);
} while (x != v && y != n);
C.back().push_back(v);
}
}
else if (dfsReach[v] > dfsReach[n])
dfsReach[v] = dfsReach[n];
}
int main ()
{
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
size_t N, m;
fin >> N >> m;
vector <vector <size_t>> G(N+1), C;
vector <size_t> dfsIndex(N+1, 0), dfsReach(N+1);
for (; m; --m)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (size_t v = 1; v <= N; ++v)
if (dfsIndex[v] == 0)
dfs (v, 0, dfsReach, dfsIndex, G, C);
fout << C.size() << '\n';
for (auto &component : C)
{
for (auto &vertex : component)
fout << vertex << ' ';
fout << '\n';
}
fout.close();
return EXIT_SUCCESS;
}