Pagini recente » Cod sursa (job #3291309) | Cod sursa (job #2690753) | Cod sursa (job #1879242) | Cod sursa (job #3239518) | Cod sursa (job #1355839)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#define mp make_pair
#define pb push_back
#define Mn(a, b) ((a) < (b) ? (a) : (b))
#define NMAX 100003
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m,i,nrcmp,ord[NMAX],low[NMAX],nmb,x,y,nrfii,art[NMAX];
vector <int> v[NMAX],c[NMAX];
stack < pair <int, int> > st;
void ins_biconex(int x, int y)
{
int fi,sc;
do
{
fi=st.top().first;
sc=st.top().second;
c[nrcmp].pb(fi);
c[nrcmp].pb(sc);
st.pop();
}
while(fi!=x || sc !=y);
}
void biconex (int nod, int tata)
{
ord[nod]=low[nod]=++nmb;
vector <int>::iterator it;
for (it=v[nod].begin(); it!=v[nod].end(); ++it)
{
if (*it==tata) continue;
if (!ord[*it])
{
// if(nod==1) nrfii++;
st.push(mp(nod,*it)); // introduc in stiva muchiile
biconex(*it, nod);
low[nod]=Mn(low[nod],low[*it]);
if (low[*it]>=ord[nod]) // nod este punct de articulatie si toate muchiile intre nod si *it fac parte dintr-o componenta biconexa
{
if (nod!=1) art[nod]=1;
nrcmp++;
ins_biconex(nod, *it);
}
}
else low[nod]=Mn(low[nod],ord[*it]); // (nod,*it) este muchie de intoarcere
}
}
int main()
{
in>>n>>m;
for (i=1;i<=m;i++)
{
in>>x>>y;
v[x].pb(y);
v[y].pb(x);
}
biconex(1,0);
//if (nrfii>=2) art[1]=1; verific daca nodul 1 este punct de articulatie
out<<nrcmp<<"\n";
for (i=1;i<=nrcmp;i++)
{
sort(c[i].begin(), c[i].end());
c[i].erase( unique (c[i].begin(), c[i].end()),c[i].end()); // elimin duplicitatile
for(vector<int>::iterator it=c[i].begin();it!=c[i].end(); ++it)
out<<*it<<" ";
out<<"\n";
}
}