Pagini recente » Cod sursa (job #368686) | Cod sursa (job #1021757) | Cod sursa (job #2860739) | Cod sursa (job #2838629) | Cod sursa (job #2368563)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 100002;
int N,M;
int x,y;
int disc[NMAX],d;
int low[NMAX];
bool viz[NMAX];
vector <int> Ad[NMAX];
vector <int> A;
vector <int> S;
int nr_comp;
vector <int> Comp[NMAX];
void DFSA(int nod,int parent)
{
//viz[nod]=1;
disc[nod]=low[nod]=++d;
for(int i=0;i<Ad[nod].size();++i)
{
int w=Ad[nod][i];
if(!disc[w])
{
S.push_back(w);
DFSA(w,nod);
low[nod]=min(low[nod],low[w]);
if(low[w] >= disc[nod])
{
++nr_comp;
S.push_back(nod);
while(!S.empty() && S.back()!=w)
{
Comp[nr_comp].push_back(S.back());
S.pop_back();
}
if(!S.empty())
{
Comp[nr_comp].push_back(S.back());
S.pop_back();
}
}
}
else if(w!=parent) low[nod]=min(low[nod],disc[w]);
}
}
void Read()
{
fin>>N>>M;
for(int i=1;i<=M;++i)
{
fin>>x>>y;
Ad[x].push_back(y);
Ad[y].push_back(x);
}
DFSA(1,0);
fout<<nr_comp<<"\n";
for(int i=1;i<=nr_comp;++i){
for(int j=0;j<Comp[i].size();++j)
fout<<Comp[i][j]<<" ";
fout<<"\n";}
}
int main()
{
Read();
return 0;
}