Pagini recente » Profil iamgroot8989 | Diferente pentru utilizator/manuelciosici intre reviziile 4 si 2 | Rezultatele filtrării | Borderou de evaluare (job #1346134) | Cod sursa (job #2722186)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
const int N = 1e5 + 5;
int n, m;
int nr_componente, nr_noduri, top;
int id[N], l[N], s[N];
vector <int> v[N], c[N];
void dfs(int nod) {
id[nod] = l[nod] = ++nr_noduri;
s[++top] = nod;
for (auto it : v[nod]) {
if (!id[it]) {
dfs(it);
l[nod] = min(l[nod], l[it]);
if (l[it] == id[nod]) {
++nr_componente;
while (s[top] != it) {
c[nr_componente].push_back(s[top]);
--top;
}
--top;
c[nr_componente].push_back(nod);
c[nr_componente].push_back(it);
}
} else {
l[nod] = min(l[nod], id[it]);
}
}
}
int main() {
cin >> n >> m;
int x, y;
for (int i = 1; i <= m; ++i) {
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
if (!id[i]) {
dfs(i);
}
}
cout << nr_componente << '\n';
for (int i = 1; i <= nr_componente; ++i) {
sort (c[i].begin(), c[i].end());
for (auto it : c[i])
cout << it << ' ';
cout << '\n';
}
return 0;
}