Pagini recente » Cod sursa (job #2679689) | Cod sursa (job #1782750) | Cod sursa (job #733396) | Cod sursa (job #1098638) | Cod sursa (job #2664403)
#include <fstream>
#include <stack>
#include <vector>
constexpr auto max_n = 100005;
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
vector<int> graph[max_n];
stack<pair<int, int>> stk;
int level[max_n];
int above[max_n];
vector<vector<int>> sub_graphs;
void handle_sub_graph(const pair<int, int> nodes)
{
vector<int> con;
int tx, ty;
do
{
tx = stk.top().first;
ty = stk.top().second;
stk.pop();
con.push_back(ty);
} while (tx != nodes.first || ty != nodes.second);
con.push_back(tx);
sub_graphs.push_back(con);
}
void dfs(const int node, const int lv)
{
level[node] = lv;
above[node] = lv;
for (auto neighbor : graph[node])
{
if (level[neighbor] == -1)
{
stk.push(make_pair(node, neighbor));
dfs(neighbor, lv + 1);
above[node] = min(above[node], above[neighbor]);
if (above[neighbor] >= level[node])
handle_sub_graph(make_pair(node, neighbor));
}
else
above[node] = min(above[node], level[neighbor]);
}
}
int main()
{
fin >> n >> m;
for (auto i = 0; i < m; i++)
{
int x, y;
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
for (auto i = 0; i <= n; i++)
level[i] = -1;
dfs(1, 0);
fout << sub_graphs.size() << "\n";
for (const auto& sub_graph : sub_graphs)
{
for (auto node : sub_graph)
fout << node << " ";
fout << "\n";
}
return 0;
}