Pagini recente » Cod sursa (job #848860) | Cod sursa (job #185889) | Cod sursa (job #1440982) | Cod sursa (job #874056) | Cod sursa (job #2124271)
#include <iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
#define N 100100
#define mp make_pair
#define f first
#define s second
#define pb push_back
int c[N],niv[N],low[N],i,j,n,x,y,m,r,nr_c,viz[N];
vector<int>a[N];
vector<vector<int> >sol;
stack<pair<int,int> > st;
void add(int x,int y)
{
++nr_c;
int a,b;
vector<int>curr;
curr.pb(x);curr.pb(y);
c[x]=nr_c;c[y]=nr_c;
while(st.top().f!=x || st.top().s!=y)
{
a=st.top().f,b=st.top().s;
st.pop();
if(c[a]!=nr_c)
{
curr.pb(a);
c[a]=nr_c;
}
if(c[b]!=nr_c)
{
c[b]=nr_c;
curr.pb(b);
}
}
st.pop();
sol.pb(curr);
}
void df(int k,int t)
{
int nod;
low[k]=niv[k];
viz[k]=1;
for(int it=0;it<a[k].size();++it)
{
nod=a[k][it];
if(nod!=t)
{
if(!viz[nod])
{
niv[nod]=niv[k]+1;
st.push(mp(k,nod));
df(nod,k);
low[k]=min(low[k],low[nod]);
if(low[nod]>=niv[k])
add(k,nod);
}
else
low[k]=min(low[k],niv[nod]);
}
}
}
int main()
{
ifstream f("conex.in");
f>>n>>m;
for(i=0;i<m;++i)
{
f>>x>>y;
a[x].pb(y);
a[y].pb(x);
}
for(i=1;i<=n;++i)
if(!c[i])
{
niv[i]=0;
df(i,0);
}
ofstream g("conex.out");
g<<nr_c<<'\n';
for(i=0;i<sol.size();++i)
{
for(j=0;j<sol[i].size();++j)
g<<sol[i][j]<<" ";
g<<'\n';
}
return 0;
}