Pagini recente » Cod sursa (job #1068896) | Cod sursa (job #1347737) | Cod sursa (job #3277718) | Cod sursa (job #2090569) | Cod sursa (job #614326)
Cod sursa(job #614326)
#include<fstream>
#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;
void citeste()
{
ifstream fin(infile);
int x,y;
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>x>>y;
v[x].pb(y);
v[y].pb(x);
}
fin.close();
}
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);
sol.pb(aux);//adaug componenta biconexa
}
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()
{
ofstream fout(outfile);
fout<<sol.size()<<'\n';
for(unsigned int i=0;i<sol.size();++i)
{
sort(sol[i].begin(),sol[i].end());
int ant = -1;
for(unsigned int j=0; j<sol[i].size(); ++j)
if(sol[i][j]!=ant)
{
fout<<sol[i][j]<<" ";
ant = sol[i][j];
}
fout<<'\n';
}
fout.close();
}
int main()
{
citeste();
df(1,0,1);
afiseaza();
return 0;
}