Pagini recente » Cod sursa (job #637213) | Cod sursa (job #2114290) | Cod sursa (job #2533286) | Cod sursa (job #14273) | Cod sursa (job #2470493)
#include <bits/stdc++.h>
#define N_MAX 100000
using namespace std;
bool visited[N_MAX + 1];
size_t visitedNodeTime[N_MAX + 1];
size_t lowestReachableNodeTime[N_MAX + 1];
stack<size_t> nodesStack;
size_t TIME = 1;
vector<vector<size_t>> graph(N_MAX, vector<size_t>());
vector<vector<size_t>> biconnectedComponents;
void biconnected_components(size_t node, size_t parent)
{
visited[node] = true;
visitedNodeTime[node] = TIME;
lowestReachableNodeTime[node] = TIME;
++TIME;
nodesStack.push(node);
for(auto& neighbour : graph[node])
{
if(neighbour == parent) continue;
if(!visited[neighbour])
{
biconnected_components(neighbour, node);
lowestReachableNodeTime[node] = min(lowestReachableNodeTime[node], lowestReachableNodeTime[neighbour]);
if(visitedNodeTime[node] <= lowestReachableNodeTime[neighbour])
{
vector<size_t> biconnectedComponent;
nodesStack.push(node);
do {
biconnectedComponent.push_back(nodesStack.top());
nodesStack.pop();
} while(nodesStack.top() != node);
biconnectedComponents.push_back(biconnectedComponent);
}
}
else lowestReachableNodeTime[node] = min(lowestReachableNodeTime[node], visitedNodeTime[neighbour]);
}
return;
}
int main()
{
size_t N, M, x, y;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin >> N >> M;
for(size_t i = 1; i <= M; ++i)
{
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
for(size_t i = 1; i <= N; ++i)
{
if(!visited[i]) biconnected_components(i, 0);
}
fout << biconnectedComponents.size() << '\n';
for(auto& biconnectedComponent : biconnectedComponents)
{
for(auto& node : biconnectedComponent) fout << node << " ";
fout << '\n';
}
return 0;
}