Pagini recente » Cod sursa (job #1819955) | Cod sursa (job #1006197) | Cod sursa (job #1177478) | Cod sursa (job #2908726) | Cod sursa (job #1142864)
#include<fstream>
#include<vector>
#include<stack>
#include<utility>
#define NMAX 200010
#define f first
#define s second
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> a[NMAX], comp[NMAX];
stack<pair<int, int> > s;
int n, m, nrcomp, rad, nrad, t[NMAX], niv[NMAX], sus[NMAX], vz[NMAX];
void Citeste()
{
int i, x, y;
f>>n>>m;
for (i=1; i<=m; ++i)
{
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
}
void Extrage(int x, int y)
{
pair<int, int> pr;
++nrcomp;
do
{
pr=s.top();
if (x!=pr.f)
{
comp[nrcomp].push_back(pr.s);
s.pop();
}
else comp[nrcomp].push_back(pr.s);
}while (x!=pr.f && y!=pr.s);
}
void DFS(int nod)
{
int i, fiu;
vz[nod]=1;
for (i=0; i<a[nod].size(); ++i)
{
fiu=a[nod][i];
if (vz[fiu]) sus[nod]=min(sus[nod], niv[fiu]);
else
{
t[fiu]=nod; niv[fiu]=niv[nod]+1; sus[fiu]=niv[fiu]; s.push(make_pair(nod, fiu));
DFS(fiu);
sus[nod]=min(sus[nod], sus[fiu]);
if (sus[fiu]>=niv[t[fiu]])
Extrage(t[nod], nod);
}
}
}
void Solve()
{
int i;
for (i=1; i<=n; ++i)
if (!vz[i])
{
t[i]=-1; niv[i]=1; sus[i]=1; s.push(make_pair(-1, 1));
DFS(i);
}
}
void Scrie()
{
int i, j;
g<<nrcomp<<"\n";
for (i=1; i<=nrcomp; ++i)
{
for (j=0; j<comp[i].size(); ++j) g<<comp[i][j]<<" ";
g<<"\n";
}
}
int main()
{
Citeste();
Solve();
Scrie();
f.close();
g.close();
return 0;
}