Pagini recente » Cod sursa (job #1932166) | Cod sursa (job #377330) | Cod sursa (job #1533699) | Cod sursa (job #2680591) | Cod sursa (job #2176234)
#include <bits/stdc++.h>
using namespace std;
#define N 100010
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
int n, m, low[N], viz[N], k, ans, cnt, AP[N];
vector <int> v[N];
void dfs(int q, int pr){
low[q] = viz[q] = ++k;
for (auto it: v[q]){
if (it == pr) continue;
if (!viz[it]){
if (q == 1) cnt++;
dfs(it, q);
low[q] = min(low[q], low[it]);
if (low[it] >= viz[q]){
if (!AP[q]) ans++;
AP[q]++;
}
}
else low[q] = min(low[q], viz[it]);
}
}
void dfsafis(int q, int src){
viz[q] = 1;
if (q != src) fout << q << " ";
if (AP[q] && q != src) return;
for (auto it: v[q]){
if (!viz[it]){
if (q == src) fout << "\n" << q << " ";
dfsafis(it, src);
}
}
}
int main(){
fin >> n >> m;
for (int i=1; i<=m; i++){
int x, y;
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, -1);
AP[1] = cnt - 1;
for (int i=1; i<=n; i++) viz[i] = 0;
fout << ans + 1;
for (int i=1; i<=n; i++){
if (AP[i]) dfsafis(i, i);
}
return 0;
}