Pagini recente » Cod sursa (job #2139528) | Cod sursa (job #1828051) | Cod sursa (job #2086957) | Cod sursa (job #1724124) | Cod sursa (job #1143107)
#include<fstream>
#include<iostream>
#include<stack>
#include<vector>
#include<set>
#include<utility>
#define NMAX 100010
#define f first
#define s second
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, nr=0, vz[NMAX], t[NMAX], sus[NMAX], niv[NMAX];
vector<int> a[NMAX];
set<int> comp[NMAX];
stack<pair<int, int> > s;
void Citeste()
{
int x, y, m;
f>>n>>m;
while (m--)
{
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
}
void Extrage(int x, int y)
{
pair<int, int> pr;
++nr;
do
{
pr=s.top(); s.pop();
comp[nr].insert(pr.f);
comp[nr].insert(pr.s);
}while ((pr.f!=x || pr.s!=y) && (pr.s!=x || pr.f!=y));
}
void DFS(int nod)
{
int i, fiu;
sus[nod]=niv[nod]; 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
{
s.push(make_pair(nod, fiu)); niv[fiu]=niv[nod]+1; t[fiu]=nod;
DFS(fiu);
sus[nod]=min(sus[nod], sus[fiu]);
if (sus[fiu]>=niv[nod])
Extrage(nod, fiu);
}
}
}
void Solve()
{
int i;
for (i=1; i<=n; ++i)
if (!vz[i])
{
t[i]=-1; niv[i]=1;
DFS(i);
}
}
void Scrie()
{
int i;
set<int> :: iterator is;
g<<nr<<"\n";
for (i=1; i<=nr; ++i)
{
for (is=comp[i].begin(); is!=comp[i].end(); ++is) g<<(*is)<<" ";
g<<"\n";
}
}
int main()
{
Citeste();
Solve();
Scrie();
f.close();
g.close();
return 0;
}