Pagini recente » Cod sursa (job #648748) | Cod sursa (job #1721921) | Cod sursa (job #1374714) | Cod sursa (job #2157948) | Cod sursa (job #2569484)
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 1e5 + 1;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N, M;
vector<vector<int>> graph(N_MAX, vector<int>());
int id[N_MAX], low[N_MAX], t;
stack<int> node_stack;
vector<vector<int>> sol;
void dfs_bcc(int node, int parent)
{
++t;
id[node] = t;
low[node] = t;
node_stack.push(node);
for(auto& next : graph[node])
{
if(next == parent) continue;
if(id[next] != 0)
low[node] = min(low[node], id[next]);
else
{
dfs_bcc(next, node);
low[node] = min(low[node], low[next]);
if(id[node] <= low[next])
{
sol.push_back(vector<int>());
sol.back().push_back(node);
sol.back().push_back(next);
while(node_stack.top() != next)
{
sol.back().push_back(node_stack.top());
node_stack.pop();
}
node_stack.pop();
}
}
}
}
int main()
{
fin >> N >> M;
for(int x, y, i = 1; i <= M; ++i)
{
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
dfs_bcc(1, -1);
fout << sol.size() << '\n';
for(auto& bcc : sol)
{
for(auto& node : bcc)
fout << node << ' ';
fout << '\n';
}
}