Pagini recente » Cod sursa (job #302772) | Cod sursa (job #549838) | Cod sursa (job #170630) | Cod sursa (job #2727930) | Cod sursa (job #1414448)
#include<iostream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<iomanip>
#include<bitset>
using namespace std;
const int N = 110000;
int n, m, ver[N], f[N], niv[N], nivmin[N], lanti[N];
vector<int> v[N];
int st[N], top;
vector<vector<int> > rez;
void df(int nod) {
f[nod] = 1;
for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) if(!f[*it]) {
niv[*it] = niv[nod] + 1;
df(*it);
}
}
void cb(int nod) {
f[nod] = 1;
nivmin[nod] = niv[nod];
st[++top] = nod;
for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) {
if(f[*it]) {
nivmin[nod] = min(nivmin[nod], niv[*it]);
if((niv[*it] - niv[nod]) % 2 == 0)
lanti[nod] = 1;
}
else {
cb(*it);
nivmin[nod] = min(nivmin[nod], nivmin[*it]);
if(nivmin[*it] >= niv[nod]) {
int imp = 0;
vector<int> el;
while(1) {
if(lanti[st[top]])
imp = 1;
el.push_back(st[top]);
--top;
if(st[top + 1] == *it)
break;
}
el.push_back(nod);
if(imp)
for(int i = 0; i < el.size(); ++i)
ver[el[i]] = 1;
rez.push_back(el);
}
}
}
}
int main() {
int i;
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
cin >> n >> m;
for(i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for(i = 1; i <= n; ++i) if(!f[i])
df(1);
memset(f, 0, sizeof(f));
for(i = 1; i <= n; ++i) if(!f[i])
cb(i);
cout << rez.size() << "\n";
for(vector<vector<int> >::iterator it = rez.begin(); it != rez.end(); ++it) {
for(i = 0; i < it->size(); ++i)
cout << (*it)[i] << " ";
cout << "\n";
}
return 0;
}