Pagini recente » Cod sursa (job #637217) | Cod sursa (job #1238014) | Cod sursa (job #2411613) | Cod sursa (job #2581924) | Cod sursa (job #2470524)
#include <fstream>
#include <vector>
#include <string>
#define N_MAX 100000 + 1
using namespace std;
size_t N, M;
vector<vector<size_t>> graph(N_MAX, vector<size_t>());
size_t nodeStack[N_MAX];
size_t stackSize = 0;
size_t time = 1;
size_t nodeTime[N_MAX];
size_t lowestTime[N_MAX];
vector<vector<size_t>> biconnectedComponents;
vector<size_t> get_biconnected_component(size_t first, size_t last)
{
vector<size_t> biconnectedComponent;
while(nodeStack[stackSize] != first)
{
biconnectedComponent.push_back(nodeStack[stackSize]);
--stackSize;
}
biconnectedComponent.push_back(first);
return biconnectedComponent;
}
void DFS(size_t node, size_t parent)
{
nodeTime[node] = time;
lowestTime[node] = time;
++time;
nodeStack[++stackSize] = node;
for(auto& neightbour : graph[node])
{
if(neightbour == parent) continue;
if(nodeTime[neightbour] == 0)
{
DFS(neightbour, node);
lowestTime[node] = min(lowestTime[node], lowestTime[neightbour]);
if(nodeTime[node] <= lowestTime[neightbour])
{
biconnectedComponents.push_back(get_biconnected_component(node, neightbour));
}
}
else lowestTime[node] = min(lowestTime[node], nodeTime[neightbour]);
}
}
void read_graph_from_file()
{
ifstream fin("biconex.in");
fin >> N >> M;
size_t x, y;
for(size_t i = 1; i <= M; ++i)
{
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
return;
}
void print_biconnected_components_to_file()
{
ofstream fout("biconex.out");
fout << biconnectedComponents.size() << '\n';
for(auto& biconnectedComponent : biconnectedComponents)
{
for(auto& node : biconnectedComponent) fout << node << ' ';
fout << '\n';
}
}
int main()
{
read_graph_from_file();
for(size_t i = 1; i <= N; ++i)
{
if(nodeTime[i] == 0) DFS(i, 0);
}
print_biconnected_components_to_file();
}