Pagini recente » Cod sursa (job #1972358) | Cod sursa (job #2955929) | Cod sursa (job #2069055) | Cod sursa (job #2770072) | Cod sursa (job #928997)
Cod sursa(job #928997)
#include<fstream>
#include<vector>
#include<utility>
#include<stack>
#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);
}while (pr.s!=nod || pr.f!=x);
if (nr==1) a[comp].push_back(pr.f);
++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)
{
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;
}