Pagini recente » Cod sursa (job #380464) | Cod sursa (job #3221820) | Cod sursa (job #1914682) | Cod sursa (job #2552278) | Cod sursa (job #613297)
Cod sursa(job #613297)
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
#define infile "biconex.in"
#define outfile "biconex.out"
#define n_max 100005
#define min(x,y) x<y ? x : y
#define pb push_back
#define mkp make_pair
using namespace std;
void citeste();
void rezolva();
void afiseaza();
vector < int > v[n_max];//graful
stack < pair<int, int> > st;//stiva
vector < vector < int> > sol;//solutia
int dfn[n_max], low[n_max];
int n,m, nrsol;
void citeste()
{
freopen(infile,"r",stdin);
int x,y;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
v[x].pb(y);
v[y].pb(x);
}
fclose(stdin);
}
void extrage(int x, int y)
{
pair < int, int> muchie;
vector< int > aux;
do
{
muchie = st.top();
st.pop();
aux.pb(muchie.first);
aux.pb(muchie.second);
} while(muchie.first !=x || muchie.second !=y);
sort(aux.begin(), aux.end());//sortez
aux.erase( unique(aux.begin(),aux.end()), aux.end() );//elimin duplicatele consecutive
sol.pb(aux);//adaug componenta biconexa
nrsol++;
}
void df(int x, int t, int h)
{
dfn[x] = h;
low[x] = h;
int nodc;
vector < int > ::iterator it;
for(it = v[x].begin(); it!=v[x].end(); ++it)
{
nodc = *it;
if(nodc!=t)
{
if(!dfn[nodc])//muchie din arbore
{
st.push(mkp(x,nodc));
df(nodc,x,h+1);
low[x] = min(low[x],low[nodc]);
if(dfn[x] <= low[nodc])//nodc este punct de articulatie
extrage(x,nodc);
}
else if(dfn[x] > dfn[nodc])//muchie de intoarcere
{
st.push(mkp(x,nodc));
low[x] = min(low[x],low[nodc]);
}
}
}
}
void afiseaza()
{
freopen(outfile,"w",stdout);
printf("%d\n",nrsol);
for(unsigned int i=0;i<sol.size();++i)
{
for(unsigned int j=0; j<sol[i].size(); ++j)
printf("%d ",sol[i][j]);
printf("\n");
}
fclose(stdout);
}
int main()
{
citeste();
df(1,0,1);
afiseaza();
return 0;
}