Pagini recente » Cod sursa (job #1657503) | Cod sursa (job #427045) | Cod sursa (job #2448618) | Cod sursa (job #1221851) | Cod sursa (job #1639752)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <utility>
constexpr int kMaxN = 100000;
int n, m;
std::vector<int> edges[kMaxN+1];
int discovery_time[kMaxN+1], low[kMaxN+1];
std::vector<std::vector<int> > biconex_componenets;
std::stack<int> S;
int static_time;
void dfs(int x)
{
++static_time;
discovery_time[x] = static_time;
low[x] = static_time;
S.push(x);
for(auto y : edges[x]) {
if(discovery_time[y] == 0) {
dfs(y);
if(discovery_time[x] == low[y]) {
std::vector<int> temp;
while(S.top() != y) {
temp.push_back(S.top());
S.pop();
}
temp.push_back(y);
S.pop();
temp.push_back(x);
biconex_componenets.push_back(std::move(temp));
}
else low[x] = std::min(low[x], low[y]);
}
else { // a back edge
low[x] = std::min(low[x], discovery_time[y]);
}
}
if(low[x] == discovery_time[x]) S.pop();
}
int main()
{
std::ifstream in("biconex.in");
std::ofstream out("biconex.out");
in>>n>>m;
for(int x, y, i = 1; i <= m; ++i) {
in>>x>>y;
edges[x].push_back(y);
edges[y].push_back(x);
}
for(int i = 1; i <= n; ++i) {
if(discovery_time[i] == 0) dfs(i);
}
out<<biconex_componenets.size()<<'\n';
for(auto& bc : biconex_componenets) {
for(auto x : bc) out<<x<<' ';
out<<'\n';
}
return 0;
}