Pagini recente » Cod sursa (job #934057) | Cod sursa (job #886010) | Cod sursa (job #2383677) | Cod sursa (job #2062415) | Cod sursa (job #775607)
Cod sursa(job #775607)
/* componente biconexe */
#include<fstream>
#include<cstdio>
#include<cstdlib>
#include<list>
#include<cmath>
#include<stack>
#include<vector>
using namespace std;
const char infile[]="biconex.in";
const char outfile[]="biconex.out";
int n,m,i,j,nrcbc;
list<int> a[200001],q;
int niv[100001],low[100001];
stack< pair<int,int> > stiva;
vector< vector<int> > bigV;
vector<int> v;
ifstream f(infile);
ofstream g(outfile);
void cbconex(int x, int y)
{v.clear();
pair<int, int> p;
do{
p=stiva.top();
stiva.pop();
v.push_back(p.second);
}while(p.first!=x && p.second!=y);
v.push_back(p.first);
bigV.push_back(v);
nrcbc++;
}
void depth(int x, int father=0)
{list<int>::iterator it;
low[x]=niv[x];
for(it=a[x].begin(); it!=a[x].end(); it++)
{if(*it ==father)
continue;
if(niv[*it]==0)
{stiva.push(make_pair(x,*it));
niv[*it]=niv[x]+1;
depth(*it,x);
if(low[x]>low[*it])
low[x]=low[*it];
if(niv[x]<=low[*it])
cbconex(x,*it);
}
else
{low[x]=min(low[x],low[*it]);}
}
}
int main()
{f>>n>>m;
int x,y;
for(i=1; i<=m; i++)
{f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);}
for(i=1; i<=n; i++)
if(niv[i]==0)
{niv[i]=1;
depth(i,0);}
g<<nrcbc<<endl;
for(i=0; i<bigV.size(); i++)
{for(j=(bigV[i].size()-1); j>=0; j--)
g<<bigV[i][j]<<" ";
g<<endl;}
f.close();
g.close();
return 0;
}