Pagini recente » Cod sursa (job #852332) | Cod sursa (job #504973) | Cod sursa (job #724273) | Cod sursa (job #2700032) | Cod sursa (job #2796480)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int N = 100010;
vector<int> v[N], ans[N];
int intoarcere[N], nivel[N], viz[N], st[N];
int top, nr_sol, n, m, x, y;
void dfs(int nod, int tata) {
intoarcere[nod] = nivel[nod] = nivel[tata] + 1;
viz[nod] = 1;
top++;
st[top] = nod;
for (auto fiu: v[nod]) {
if (fiu == tata)
continue;
if (viz[fiu]) // suntem intr-o muchie de intoarcere
{
intoarcere[nod] = min(intoarcere[nod], nivel[fiu]);
continue;
}
dfs(fiu, nod);
intoarcere[nod] = min(intoarcere[nod], intoarcere[fiu]);
if (intoarcere[fiu] >= nivel[nod]) {
nr_sol++;
while (st[top + 1] != fiu) {
ans[nr_sol].push_back(st[top]);
top--;
}
ans[nr_sol].push_back(nod);
}
}
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; i++) {
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs(i, 0);
fout << nr_sol << '\n';
for (int i = 1; i <= nr_sol; i++) {
for (auto it: ans[i])
fout << it << " ";
fout << '\n';
}
return 0;
}