Pagini recente » Cod sursa (job #492802) | Cod sursa (job #1118179) | Cod sursa (job #361642) | Cod sursa (job #746994) | Cod sursa (job #929010)
Cod sursa(job #929010)
#include<fstream>
#include<vector>
#include<utility>
#include<stack>
#include<algorithm>
#define f first
#define s second
#define NMAX 100010
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m, nr=0, comp=1, ns=0, dfn[NMAX], low[NMAX];
vector<int> v[NMAX], a[NMAX];
stack<pair <int, int> > S;
void Citeste()
{
int i, x, y;
f>>n>>m;
for (i=1; i<=m; ++i)
{
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
}
void Scoate(int x, int nod)
{
pair< int, int > pr;
int nr=0;
do
{
pr=S.top(); S.pop(); ++nr;
a[comp].push_back(pr.s);
a[comp].push_back(pr.f);
}while (pr.s!=nod || pr.f!=x);
++comp;
}
void Biconex(int nod, int tata)
{
int i, x;
dfn[nod]=low[nod]=++nr;
for (i=0; i<v[nod].size(); ++i)
{
x=v[nod][i];
if (x!=tata && dfn[x]<dfn[nod])
{
S.push( make_pair(x, nod) );
}
if (!dfn[x])
{
Biconex(x, nod);
low[nod]=min(low[nod], low[x]);
if (low[x]>=dfn[nod])
Scoate(x, nod);
}
else
if (x!=tata) low[nod]=min(low[nod], dfn[x]);
}
}
void Scrie()
{
int i, j;
g<<comp-1<<"\n";
for (i=1; i<comp; ++i)
{
sort(a[i].begin(), a[i].end());
a[i].erase(unique(a[i].begin(), a[i].end()), a[i].end());
for (j=0; j<a[i].size(); ++ j) g<<a[i][j]<< " ";
g<<"\n";
}
}
int main()
{
Citeste();
Biconex(1, -1);
Scrie();
f.close();
g.close();
return 0;
}