Pagini recente » Cod sursa (job #3354558) | Cod sursa (job #1723501) | Cod sursa (job #3189692) | Cod sursa (job #3342987) | Cod sursa (job #3346963)
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int nmax = 1e5;
vector<int>v[nmax + 1];
int d[nmax + 1], low[nmax + 1], timer,bccs;
stack<pii>s;
vector<pii>b[nmax+1];
void get_bcc(pii e){
bccs++;
while(s.top()!=e){
b[bccs].pb(s.top());
s.pop();
}
b[bccs].pb(e);
s.pop();
}
void dfs (int nod, int pr) {
d[nod] = low[nod] = ++timer;
int cnt = 0;
for (int i : v[nod]) {
if (i == pr)
continue;
if (d[i])
low[nod] = min (low[nod], d[i]);
else {
cnt++;
s.push({nod,i});
dfs (i, nod);
low[nod] = min (low[nod], low[i]);
if(low[i]>=d[nod] || (nod==1 && cnt>=2))
get_bcc({nod,i});
}
}
}
vector<int>now;
int main() {
int n,m;
fin>>n>>m;
while(m--){
int st,dr;
fin>>st>>dr;
v[st].pb(dr);
v[dr].pb(st);
}
dfs(1,1);
fout<<bccs<<'\n';
for(int i=1;i<=bccs;i++){
now.clear();
for(pii j:b[i])
now.pb(j.first),now.pb(j.second);
sort(now.begin(),now.end());
now.erase(unique(now.begin(),now.end()),now.end());
for(int j:now)
fout<<j<<' ';
fout<<'\n';
}
return 0;
}