Pagini recente » Cod sursa (job #1866135) | Cod sursa (job #2844213) | Cod sursa (job #2553257) | Cod sursa (job #700140) | Cod sursa (job #1910228)
#include <bits/stdc++.h>
using namespace std;
const int nMax = 1e5 + 2;
int n, m, low[nMax], in[nMax];
vector<int>g[nMax];
vector<vector<int>>comp;
stack<pair<int, int>>st;
void Citire() {
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
g[x].push_back(y), g[y].push_back(x);
}
}
void add_comp(int nod, int fiu) {
comp.push_back(vector<int>());
int a, b;
do {
a = st.top().first;
b = st.top().second;
st.pop();
comp.back().push_back(a);
comp.back().push_back(b);
}
while (a != nod or b != fiu);
}
void tarjan(int nod, int father, int level = 1) {
in[nod] = level;
low[nod] = level;
for (const auto& fiu : g[nod]) {
if (fiu == father)
continue;
if (!in[fiu]) {
st.emplace(nod, fiu);
tarjan(fiu, nod, level + 1);
low[nod] = min(low[nod], low[fiu]);
if (low[fiu] >= level) {
add_comp(nod, fiu);
}
}
else {
low[nod] = min(low[nod], in[fiu]);
}
}
}
void make_unique(vector<int>&that) {
sort(that.begin(), that.end());
that.resize(unique(that.begin(), that.end()) - that.begin());
}
void print(const vector<int>&that) {
for (const auto& itr : that)
printf("%d ", itr);
printf("\n");
}
void PrintComps() {
printf("%d\n", comp.size());
for (auto& itr : comp) {
make_unique(itr);
print(itr);
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
Citire();
tarjan(1, 0, 1);
PrintComps();
}