Pagini recente » Cod sursa (job #1685522) | Cod sursa (job #2470747) | Cod sursa (job #2892931) | Cod sursa (job #1379619) | Cod sursa (job #1919377)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int maxn = 1e5 + 5;
vector <int> G[maxn], Comp[maxn];
stack < pair <int,int> > Stk;
int Low[maxn], Lev[maxn], ans;
void Get_comp (int x, int y) {
int a, b;
ans++;
do {
a = Stk.top().first;
b = Stk.top().second;
Stk.pop();
Comp[ans].push_back(b);
} while (a != x || b != y);
Comp[ans].push_back(a);
}
void Dfs (int node) {
vector <int> :: iterator it;
Low[node] = Lev[node];
for (it = G[node].begin(); it != G[node].end(); it++) {
if (Lev[*it] == 0) {
Lev[*it] = Lev[node] + 1;
Stk.push(make_pair(node, *it));
Dfs(*it);
Low[node] = min(Low[node], Low[*it]);
if (Low[*it] >= Lev[node]) Get_comp(node, *it); /// node = punct de articulatie
} else {
Low[node] = min(Low[node], Lev[*it]);
}
}
}
int main() {
ios_base :: sync_with_stdio (false);
int n, m, i, j, x, y;
fin >> n >> m;
for (i = 1; i <= m; i++) {
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
Lev[1] = 1;
Dfs(1);
fout << ans << "\n";
for (i = 1; i <= ans; i++) {
for (j = 0; j < (int) Comp[i].size(); j++) {
fout << Comp[i][j] << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}