Pagini recente » Cod sursa (job #907717) | Cod sursa (job #703392) | Cod sursa (job #194815) | Cod sursa (job #732283) | Cod sursa (job #526078)
Cod sursa(job #526078)
// Componente biconexe
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int n,m,vizitat[100],nivel[100];
vector <int> graf[100];
stack <pair<int,int> > stiva;
vector <vector <int> > C;
void read()
{
int i,x,y;
ifstream f("biconex.in");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
graf[x].push_back(y);
graf[y].push_back(x);
}
f.close();
}
void scrie_componenta(int x, int y)
{
vector <int> comp;
int i,j;
do {
i = stiva.top().first, j = stiva.top().second;
stiva.pop();
comp.push_back(i), comp.push_back(j);
}
while (i != x || j != y);
C.push_back(comp);
}
void puncte_critice(int nod, int parinte, int niv)
{
int i,x;
vizitat[nod]=niv, nivel[nod]=niv;
for(i=0;i<graf[nod].size();i++)
{
x=graf[nod][i];
if(!vizitat[x])
{
stiva.push(make_pair(x,nod));
puncte_critice(x,nod,niv+1);
if(nivel[x]<nivel[nod])
nivel[nod]=nivel[x];
if(nivel[x]>=vizitat[nod])
scrie_componenta(x,nod);
}
else
if(x!=parinte&&vizitat[x]<nivel[nod]) nivel[nod]=vizitat[x];
}
}
void solve()
{
int i;
for(i=1;i<=n;i++)
if(!vizitat[i])
puncte_critice(i,0,0);
}
void write()
{
int i,j;
ofstream g("biconex.out");
g<<C.size()<<"\n";
for(i=0;i<C.size();i++)
{
sort(C[i].begin(), C[i].end());
C[i].erase(unique(C[i].begin(), C[i].end()), C[i].end());
for(j=0;j<C[i].size();j++)
g<<C[i][j]<<" ";
g<<"\n";
}
g.close();
}
int main()
{
int i,j;
read();
solve();
write();
return 0;
}