Pagini recente » Cod sursa (job #2373545) | Cod sursa (job #130808) | Cod sursa (job #1768478) | Cod sursa (job #1237996) | Cod sursa (job #1249621)
#include <algorithm>
#include <fstream>
#include <iterator>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
vector<bool> visited;
stack<pair<int, int>> edges;
vector<vector<int>> bc, G;
vector<int> reach, level;
void dfs(const int v, const int pv, int lvl) {
visited[v] = true;
level[v] = reach[v] = lvl;
for (int u : G[v]) {
if (!visited[u]) {
edges.push(make_pair(v, u));
dfs(u, v, lvl+1);
reach[v] = min(reach[v], reach[u]);
if (reach[u] >= level[v]) {
bc.push_back(vector<int>());
pair<int, int> e;
do {
e = edges.top(); edges.pop();
bc.back().push_back(e.second + 1);
} while (e.first != v && e.second != u);
bc.back().push_back(v + 1);
}
}
else if (u != pv)
reach[v] = min(reach[v], reach[u]);
}
}
int main() {
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m; fin >> n >> m;
G.resize(n);
for (; m; --m) {
int u, v;
fin >> u >> v;
G[u-1].push_back(v-1);
G[v-1].push_back(u-1);
}
visited.resize(G.size(), false);
reach.resize(G.size());
level.resize(G.size());
for (int v = 0; v < G.size(); ++v) if(!visited[v])
dfs(v, -1, 0);
fout << bc.size() << '\n';
for (auto& c : bc) {
copy(c.begin(), c.end(), ostream_iterator<int>(fout, " "));
fout << '\n';
}
return 0;
}