Pagini recente » Cod sursa (job #487960) | Cod sursa (job #484161) | Cod sursa (job #726570) | Cod sursa (job #326306) | Cod sursa (job #1478658)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <algorithm>
#include <utility>
#define NMAX 100003
#define Min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m,dfn[NMAX],low[NMAX],start=1,x,y,nro,c;
vector<int> a[NMAX];
stack< pair<int,int> > stiva;
vector< vector<int> > comp;
void citire()
{
in >> n >> m;
for(int i=0;i<m;i++)
{
in >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
for(int i=0;i<=n;i++)
dfn[i]=-1;
}
void afisare(int x1, int y1)
{
int xx,yy;
vector<int> cont;
do
{
xx = stiva.top().first;
yy = stiva.top().second;
stiva.pop();
cont.push_back(xx);
cont.push_back(yy);
}
while((xx!=x1 || yy!=y1));
comp.push_back(cont);
}
void biconex(int nod, int tnod)
{
int fiu;
dfn[nod]=low[nod]=nro++;
for(int i=0;i<a[nod].size();i++)
{
fiu = a[nod][i];
if(fiu == tnod) { continue;}
if(dfn[fiu]==-1)
{
stiva.push(make_pair(nod,fiu));
biconex(fiu,nod);
low[nod] = Min(low[nod],low[fiu]);
if(low[fiu]>=dfn[nod])
{
// cout << nod << " " << tnod << endl;
afisare(nod,fiu);
}
}
else
low[nod] = Min(low[nod],dfn[fiu]);
}
}
void af()
{
out << comp.size() << "\n";
for(int i=0;i<comp.size();i++)
{
sort(comp[i].begin(),comp[i].end());
comp[i].resize(unique(comp[i].begin(),comp[i].end())-comp[i].begin());
for(int j=0;j<comp[i].size();j++)
out << comp[i][j] << " ";
out << "\n";
}
}
int main()
{
citire();
biconex(1,-1);
af();
return 0;
}
/*
void biconex(int nod, int tnod)
{
int fiu;
dfn[nod]=low[nod]=nro++;
for(int i=0;i<a[nod].size();i++)
{
fiu = a[nod][i];
if(fiu == tnod) { continue;}
if(dfn[fiu]==-1)
{
stiva.push(make_pair(nod,fiu));
biconex(fiu,nod);
low[nod] = Min(low[nod],low[fiu]);
if(low[fiu]>=dfn[nod])
{
cout << nod << " " << tnod << endl;
// afisare(nod,fiu);
}
}
else
low[nod] = Min(low[nod],dfn[fiu]);
}
}*/