Pagini recente » Cod sursa (job #189911) | Cod sursa (job #985390) | Cod sursa (job #2920690) | Cod sursa (job #2874083) | Cod sursa (job #2555724)
#include <bits/stdc++.h>
#define N_MAX 100000 + 1
using namespace std;
ifstream fin{"biconex.in"};
ofstream fout{"biconex.out"};
vector<vector<int>> graph(N_MAX, vector<int>());
int N, M;
vector<int> id(N_MAX, 0);
vector<int> low(N_MAX, 0);
vector<bool> visited(N_MAX, false);
vector<vector<int>> ans;
stack<int> node_stack;
int __timer__ = 0;
void DFS(int node, int parent)
{
visited[node] = true;
id[node] = low[node] = ++__timer__;
node_stack.push(node);
for(auto& next : graph[node])
{
if(next == parent) continue;
if(visited[next] == false){
DFS(next, node);
low[node] = min(low[node], low[next]);
if(id[node] <= low[next])
{
vector<int> bcc;
while(node_stack.top() != node)
{
bcc.push_back(node_stack.top());
node_stack.pop();
}
bcc.push_back(node);
ans.push_back(bcc);
}
}
else
low[node] = min(low[node], id[next]);
}
}
int main()
{
fin >> N >> M;
for(int i = 1; i <= M; ++i)
{
int x, y;
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
DFS(1, -1);
fout << ans.size() << '\n';
for(auto& bcc : ans)
{
for(auto& node : bcc)
{
fout << node << ' ';
}
fout << '\n';
}
}