Pagini recente » Cod sursa (job #1710607) | Cod sursa (job #324843) | Cod sursa (job #1292001) | Cod sursa (job #2759972) | Cod sursa (job #2590946)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int>> Graph, Comps;
vector<int> depth; // standard depth
vector<int> level; // level[i] = smallest depth I can reach from i's subtree
vector<bool> used;
stack<pair<int,int>> Stack;
void getComponent(int k, int v)
{
vector <int> currentComponent;
while (true) {
auto crt = Stack.top();
Stack.pop();
currentComponent.emplace_back(crt.second);
if (crt.first == k)
break;
}
currentComponent.emplace_back(k);
Comps.emplace_back(currentComponent);
}
void DFS(int dad, int k)
{
used[k] = true;
depth[k] = depth[dad] + 1;
level[k] = depth[k];
for (auto v : Graph[k])
if (!used[v]) {
Stack.push({k, v});
DFS(k, v);
level[k] = min(level[k], level[v]);
if (level[v] >= depth[k]) // found biconnected component
getComponent(k, v);
}
else if (v != dad) level[k] = min(level[k], depth[v]);
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin.sync_with_stdio(false);
fin.tie(0);
fout.sync_with_stdio(false);
fout.tie(0);
int N, M;
fin >> N >> M;
Graph.resize(N + 1);
depth.resize(N + 1);
level.resize(N + 1);
used.resize(N + 1);
for (int i = 0; i < M; ++i) {
int a, b;
fin >> a >> b;
Graph[a].emplace_back(b);
Graph[b].emplace_back(a);
}
for (int i = 1; i <= N; ++i)
if (!used[i]) {
Stack.push({0,i});
DFS(0, i);
Stack.pop();
}
fout << Comps.size() << "\n";
for (auto comp : Comps) {
for (auto v : comp)
fout << v << " ";
fout << "\n";
}
return 0;
}