Pagini recente » Cod sursa (job #1433395) | Cod sursa (job #1432447) | Cod sursa (job #3217121) | Cod sursa (job #1432274) | Cod sursa (job #1420482)
#include <fstream>
#include <vector>
#include <stack>
#include <unordered_set>
using Graph = std::vector<std::vector<int>>;
const int NMAX = 100005;
Graph G(NMAX);
std::vector<int> indexes(NMAX, -1);
std::vector<int> lowlinks(NMAX);
void tarjan(int node,
int parent,
std::stack<std::pair<int, int>> &st,
std::vector<std::unordered_set<int>> &comps,
int &currIndex)
{
indexes[node] = lowlinks[node] = currIndex;
for (auto &neigh : G[node]) {
// Ignorăm vecinul nodului curent care este de fapt tatăl său în
// arborele DFS, deoarece de acolo am ajuns aici oricum.
if (neigh == parent)
continue;
// Dacă nu am vizitat acest nod încă.
if (indexes[neigh] == -1) {
// Îl punem în stivă alături de tatăl său și continuăm recursiv.
st.emplace(node, neigh);
tarjan(neigh, node, st, comps, ++currIndex);
// Updatăm lowlinkul nodului curent. În acest moment am vizitat
// întreaga ramură a arborelui care pornește din vecinul curent al
// nodului.
lowlinks[node] = std::min(lowlinks[node], lowlinks[neigh]);
if (lowlinks[neigh] >= indexes[node]) {
std::unordered_set<int> comp;
int child, parent;
do {
comp.emplace((parent = st.top().first));
comp.emplace((child = st.top().second));
st.pop();
} while (parent != node || child != neigh);
comps.emplace_back(comp);
}
} else {
lowlinks[node] = std::min(lowlinks[node], lowlinks[neigh]);
}
}
}
int main()
{
std::ifstream fin{"biconex.in"};
std::ofstream fout{"biconex.out"};
int N, M;
fin >> N >> M;
for (auto i = 0; i < M; ++i) {
int x, y;
fin >> x >> y;
G[x - 1].emplace_back(y - 1);
G[y - 1].emplace_back(x - 1);
}
std::vector<std::unordered_set<int>> comps;
std::stack<std::pair<int, int>> st;
auto currIndex = -1;
for (auto i = 0; i < N; ++i)
if (indexes[i] == -1)
tarjan(i, -1, st, comps, ++currIndex);
fout << comps.size() << '\n';
for (auto &comp : comps) {
for (auto &e : comp)
fout << e + 1 << ' ';
fout << '\n';
}
return 0;
}