Pagini recente » Cod sursa (job #699687) | Cod sursa (job #2661701) | Cod sursa (job #1975506) | Cod sursa (job #2394439) | Cod sursa (job #540690)
Cod sursa(job #540690)
#include<fstream>
#include<stack>
#include<vector>
#include<iterator>
#include<algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
# define nmax 100002
# define Min(a,b) ((a)<(b)? (a):(b))
vector <int> v[nmax];
vector <vector <int> > afis;
stack <pair <int,int> > S;
int N,M,niv[nmax],low[nmax];
void citire()
{
f>>N>>M;
int i,j;
for(;M;--M)
f>>i>>j, v[i].push_back(j), v[j].push_back(i);
}
void componenta(int a,int b)
{
int x,y;
vector <int> c;
do{
x=S.top().first; y=S.top().second;
S.pop();
c.push_back(x); c.push_back(y);
}while(x!=a||y!=b);
afis.push_back(c);
}
void cbc(int nod,int nivel,int parinte)
{
niv[nod]=low[nod]=nivel;
vector <int>::const_iterator it;
for(it=v[nod].begin();it<v[nod].end();++it)
{
if(*it==parinte) continue;
if(niv[*it])
low[nod]=Min(low[nod],niv[*it]);
else
{
S.push(make_pair(nod,*it));
cbc(*it,nivel+1,nod);
low[nod]=Min(low[nod],low[*it]);
if(low[*it]>=niv[nod])
componenta(nod,*it);
}
}
}
int main()
{
citire();
int i,n,m,j,x;
for(i=1;i<=N;++i)
if(!niv[i])
cbc(1,1,-1);
n=afis.size();
for(i=0;i<n;++i) sort(afis[i].begin(),afis[i].end());
g<<n<<'\n';
for(i=0;i<n;++i)
{
m=afis[i].size();
x=0;
for(j=0;j<m;++j)
if(afis[i][j]!=x)
g<<afis[i][j]<<' ', x=afis[i][j];
g<<'\n';
}
return 0;
}