Pagini recente » Monitorul de evaluare | Cod sursa (job #2889299) | Cod sursa (job #1739802) | Cod sursa (job #1409797) | Cod sursa (job #2576599)
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
ifstream fin ("biconex.in");
ofstream fout("biconex.out");
#define cin fin
#define cout fout
#define Nmax 100010
int n;
vector < int > g[Nmax];
int sus[Nmax], jos[Nmax];
int nr = 0;
vector < int > componente[Nmax];
stack < pair < int, int > > s;
void read() {
int m;
cin >> n >> m;
while(m--) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
}
void scoateStiva(int x, int y) {
nr++;
int tx, ty;
do {
tx = s.top().first;
ty = s.top().second;
s.pop();
componente[nr].push_back(tx);
componente[nr].push_back(ty);
} while (tx != x || ty != y);
}
void DFS(int nod, int tata, int nivel) {
sus[nod] = jos[nod] = nivel;
for(const auto it : g[nod] ) {
if(it == tata) {
continue;
}
if(sus[it] == -1) {
s.push({nod, it});
DFS(it, nod, nivel+1);
jos[nod] = min(jos[nod], jos[it]);
if(jos[it] >= sus[nod]) {
scoateStiva(nod, it);
}
} else {
jos[nod] = min(jos[nod], sus[it]);
}
}
}
void solve() {
for(int i=1; i<=n; i++) {
sus[i] = -1;
}
DFS(1, 0, 0);
cout << nr << endl;
for(int i=1; i <= nr; i++) {
sort(componente[i].begin(), componente[i].end());
componente[i].erase(unique(componente[i].begin(), componente[i].end()), componente[i].end());
for(const auto it : componente[i]) {
cout << it << " ";
}
cout << endl;
}
}
int main () {
read();
solve();
}