Pagini recente » Cod sursa (job #3125981) | Cod sursa (job #2219912) | Cod sursa (job #1038619) | Cod sursa (job #1454326) | Cod sursa (job #2557828)
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 1e5 + 1;
vector<vector<int>> graph(N_MAX, vector<int>());
int N, M;
vector<int> DFS_ORDER(N_MAX, 0);
vector<int> LOW(N_MAX, 0);
stack<int> NODE_STACK;
vector<vector<int>> BICONNECTED_COMPONENTS;
int order_cnt = 0;
void dfsBiconnectedComponents(int node, int parent)
{
DFS_ORDER[node] = LOW[node] = ++order_cnt;
NODE_STACK.push(node);
for(auto& next : graph[node])
{
if(next == parent) continue;
if(DFS_ORDER[next] != 0)
LOW[node] = min(LOW[node], DFS_ORDER[next]);
else
{
dfsBiconnectedComponents(next, node);
LOW[node] = min(LOW[node], LOW[next]);
if(DFS_ORDER[node] <= LOW[next])
{
vector<int> BICONNECTED_COMPONENT;
int aux;
do
{
aux = NODE_STACK.top();
NODE_STACK.pop();
BICONNECTED_COMPONENT.push_back(aux);
} while(aux != next);
BICONNECTED_COMPONENT.push_back(node);
BICONNECTED_COMPONENTS.push_back(BICONNECTED_COMPONENT);
}
}
}
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
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);
}
dfsBiconnectedComponents(1, -1);
fout << BICONNECTED_COMPONENTS.size() << '\n';
for(auto& BICONNECTED_COMPONENT : BICONNECTED_COMPONENTS)
{
for(auto& node : BICONNECTED_COMPONENT)
{
fout << node << ' ';
}
fout << '\n';
}
}