Pagini recente » Cod sursa (job #373779) | Cod sursa (job #2979821) | Cod sursa (job #2614957) | Cod sursa (job #927448) | Cod sursa (job #1404678)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct muchie
{ int x, y;
};
vector<int> G[100001];
stack<muchie> stiva; //stiva cu muchii
set<int> sol[100001]; //solutia retinuta ca set pentru a pastra ordinea crescatoare
set<int>::iterator it;
bool viz[100001];
int nr, tata[100001], nivel[100001], L[100001];
void DFS(int nod)
{ viz[nod]=1;
L[nod]=nivel[nod];
vector<int>::iterator it;
for (it=G[nod].begin(); it!=G[nod].end(); it++)
if (*it!=tata[nod])
{
if (viz[*it]==0)
{
muchie a;
a.x=nod;
a.y=*it;
stiva.push(a);
nivel[*it]=1+nivel[nod]; //nivelul in arborele DFS
tata[*it]=nod; //tatal nodului e vf din care e descoperit
DFS(*it);
L[nod]=min(L[nod], L[*it]); //actualizam L pentru nod in cazul in care in recursivitate fiul sau a intrat intr-o componenta biconexa cu nivel mai mic
if (L[*it]>=nivel[nod]) //"=" cand e ciclu; ">" cand e muchie
{ ++nr;
int i, j;
while (i!=nod || j!=*it)
{ i=stiva.top().x;
j=stiva.top().y;
stiva.pop();
sol[nr].insert(i);
sol[nr].insert(j);
}
}
}
else
L[nod]=min(L[nod], nivel[*it]); //toate componentele unui ciclu pastreaza acelasi L=nivel primului element descoperit din ciclu
}
}
int main()
{
int n,m,i,x,y;
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
nivel[1]=1;
DFS(1);
g<<nr<<'\n';
for (i=1; i<=nr; ++i)
{ for (it=sol[i].begin(); it!=sol[i].end(); ++it)
g<<*it<<' ';
g<<'\n';
}
return 0;
}