Pagini recente » Cod sursa (job #3218146) | Cod sursa (job #209601) | Cod sursa (job #2331560) | Cod sursa (job #2653800) | Cod sursa (job #240865)
Cod sursa(job #240865)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define pb push_back
#define u first
#define v second
const int NMAX=100001;
vector<int> Adj[NMAX],a;
int N,M,nr,d[NMAX],low[NMAX];
vector< vector<int> > C;
stack< pair<int,int> > s;
vector< pair<int,int> > b;
bool U[NMAX];
void df(int vf){
vector<int>::iterator it;
int x,y;
low[vf]=d[vf];
for (it=Adj[vf].begin();it!=Adj[vf].end();++it)
if (!d[*it]){
d[*it]=d[vf]+1;
s.push(make_pair(vf,*it));
df(*it);
if (low[*it]>=d[vf])
{
++nr;
b.clear();
do {
b.pb(s.top());
x=s.top().u;
y=s.top().v;
s.pop();
}
while (x!=vf || y!=*it);
a.clear();
for (size_t i=0;i<b.size();++i)
U[b[i].u]=U[b[i].v]=false;
for (size_t i=0;i<b.size();++i){
if (!U[b[i].u]) a.pb(b[i].u);
if (!U[b[i].v]) a.pb(b[i].v);
U[b[i].u]=U[b[i].v]=true;}
C.pb(a);
}
low[vf]=min(low[vf],low[*it]);
}
else if (d[vf]-1!=d[*it]) low[vf]=min(low[vf],low[*it]);
}
int main(){
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int i,j;
fin>>N>>M;
while (M--){
fin>>i>>j;
Adj[i].pb(j);
Adj[j].pb(i);}
d[1]=1;
df(1);
fout<<nr<<'\n';
for (i=0;i<nr;++i){
for (j=0;j<(int)C[i].size();++j)
fout<<C[i][j]<<' ';
fout<<'\n';}
return 0;
}