Pagini recente » Cod sursa (job #321403) | Cod sursa (job #601349) | Cod sursa (job #601776) | Cod sursa (job #601358)
Cod sursa(job #601358)
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstring>
//#include"verificator.cpp"
#define pb push_back
struct much{
int n1,n2;};
ofstream fout("biconex.out");
int t[100005],niv[100005],low[100005],N,M,toleranta;
vector<int> G[100005];
vector<vector<int> > sol;
stack<much> S;
void cit();
void extrage(int x,int y)
{ vector<int> con;
much dummy;
do
{dummy=S.top();
S.pop();
//cout<<dummy.n1<<" "<<dummy.n2<<" ";
con.pb(dummy.n1);
con.pb(dummy.n2);
}
while(dummy.n1!=x||dummy.n2!=y);
sol.pb(con);
}
int lev=0;
void dfs(int v,int tata)
{vector<int>::iterator it;
int w;
niv[v]=++lev;
low[v]=lev;
t[v]=tata;
for(it=G[v].begin();it!=G[v].end();it++)
{ w=*it;
if(tata!=w) //daca w nu e tatal lui u
{
if(niv[w]==0) //daca w nu a fost vizitat (si este evident v->w e evident muchie de inaintare)
{
S.push((much){v,w});
dfs(w,v); //exploreaza subarborele
low[v]=min(low[v],low[w]); //vezi daca dintre fii lui v ai gasit unul din care se poate ajunge mai sus decat v si updateaza
if(niv[v]<=low[w]) //daca cel mai sus loc care in care se poate ajunge din w(si implicit din subarborele sau) este mai jos sau este v
{
extrage(v,w); //extrage componeneta biconexa
}
}
else
{if(niv[w]<niv[v]) // ca sa ni bage si muchiile invers, daca muchia de intoarcere e 2->1 sa nu bage si 1->4
{S.push((much){v,w});
//if(niv[w]>=niv[v]) cout<<v<<" "<<w<<" "<<niv[v]<<" "<<niv[w]<<"\n";
low[v]=min(low[v],niv[w]);} //vezi daca nivelul lui w este mai sus de nivelul cel mai de sus la care se poate
//ajunge din v pana la momentul respectiv si fa update.
}
}
}
}
int main()
{int i,mos=-1;;
vector<int>::iterator it;
cit();
dfs(1,0);
fout<<sol.size()<<"\n";
for(i=0;i<sol.size();i++)
{sort(sol[i].begin(),sol[i].end());
mos=-1;
for(it=sol[i].begin();it!=sol[i].end();it++)
if(*it!=mos)
{
mos=*it;
fout<<*it<<" ";
}
fout<<"\n";
}
fout.close();
return 0;
}
void cit()
{
int i,x,y;
ifstream fin("biconex.in");
fin>>N>>M;
for(i=1;i<=M;i++)
{
fin>>x>>y;
G[x].pb(y);
G[y].pb(x);
//cout<<G[x].back()<<" "<<G[y].back()<<"\n";
}
fin.close();
}