Pagini recente » Cod sursa (job #237201) | Cod sursa (job #400888) | Cod sursa (job #2621854) | Cod sursa (job #468418) | Cod sursa (job #433808)
Cod sursa(job #433808)
#include<stdio.h>
#include<vector>
#include<stack>
#include<set>
using namespace std;
#define Nmax 100010
#define fs first
#define sc second
#define mp make_pair
int N,v[Nmax],t[Nmax],niv[Nmax],lv[Nmax];
vector <int> l[Nmax];
stack < pair<int,int> > st;
vector < set<int> > comp;
void rezolv(int x,int y)
{
set<int> s;
pair<int,int> vf;
s.insert(x);
s.insert(y);
for( vf=st.top() ; vf.fs != x || vf.sc !=y ; vf=st.top())
{
s.insert(vf.fs);
s.insert(vf.sc);
st.pop();
}
comp.push_back( s );
st.pop();
}
void DF(int k,int level,int tata)
{
v[k]=1;
t[k]=tata;
niv[k]=lv[k]=level;
vector<int>::iterator it;
for(it=(l[k]).begin();it!=(l[k]).end();++it)
if ((*it)!=t[k])
{
if (!v[*it])
{
st.push( mp(k,*it) );
DF( *it , level+1 , k);
if (lv[*it] >= niv[k])
rezolv(k,*it);
}
lv[k] = min(lv[k],lv[*it]);
}
}
void afis()
{
printf("%d\n",comp.size());
set<int>::iterator it;
for(int i=0;i<(int)comp.size();++i)
{
for(it=comp[i].begin(); it!=comp[i].end() ;++it)
printf("%d ",(*it));
printf("\n");
}
}
void cit()
{
int a,b,M;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i=1;i<=M;++i)
{
scanf("%d%d",&a,&b);
l[a].push_back(b);
l[b].push_back(a);
}
}
int main()
{
cit();
DF(1,0,0);
afis();
return 0;
}