Pagini recente » Cod sursa (job #3225385) | Cod sursa (job #1510895) | Cod sursa (job #933765) | Cod sursa (job #2487291) | Cod sursa (job #2489588)
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
ifstream fin{"biconex.in"};
ofstream fout{"biconex.out"};
vector<vector<int>> graph(NMAX, vector<int>());
int N, M;
int id[NMAX], low[NMAX];
stack<int> s;
int _time = 0;
vector<vector<int>> bcs;
void biconnected(int node, int parent)
{
id[node] = low[node] = ++_time;
s.push(node);
for(auto& next : graph[node])
{
if(next == parent) continue;
if(id[next] == 0)
{
biconnected(next, node);
low[node] = min(low[node], low[next]);
if(low[next] >= id[node])
{
bcs.push_back(vector<int>());
int x;
do
{
x = s.top();
bcs.back().push_back(x);
s.pop();
}
while(x != next);
bcs.back().push_back(node);
}
}
else low[node] = min(low[node], id[next]);
}
}
int main()
{
fin >> N >> M;
for(int i = 1, x, y; i <= M; ++i)
{
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
biconnected(1, -1);
fout << bcs.size() << '\n';
for(auto& bc : bcs)
{
for(auto& node : bc) fout << node << ' ';
fout << '\n';
}
}