Pagini recente » Cod sursa (job #1780280) | Cod sursa (job #3272691) | Cod sursa (job #1679337) | Cod sursa (job #1661097) | Cod sursa (job #2781392)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconexe.in");
ofstream fout("biconexe.out");
int vizitat[100005];
int nivel[100005]; //vector ce retine nivelul la care se afla fiecare nod in graful de parcurgere DFS
int nma[100005]; //vector ce retine nivelul minim accesibil(nivelul minim al unui ascendent la care are acces printr-o muchie
// de intoarcere) de catre fiecare nod
stack<int> stiva; //stiva in care vom retine nodurile grafului in ordinea parcurgerii DFS
vector<vector<int>> biconexe; //vectorul de componente biconexe
int n, m;
//liste de adiacente
vector<vector<int>> la;
//determinare componente biconexe
void bcx(int tata)
{
vector<int> componenta;
while(!stiva.empty() && stiva.top()!=tata)
{
componenta.push_back(stiva.top());
stiva.pop();
}
componenta.push_back(tata);
biconexe.push_back(componenta);
}
//parcurgere dfs
void dfs(int x, int tata)
{
vizitat[x] = 1;
nivel[x] = nivel[tata] + 1;
nma[x] = nivel[x]; //initiaizez nma cu nivelul curent(nu stiu momentan pana la ce nivel se poate intoarce)
stiva.push(x); //adaug nodul in stiva
//fout << x << " ";
//parcurg lista de adiacente a lui x
for(int i=0; i<la[x].size(); ++i)
{
int y = la[x][i];
if (vizitat[y] == 0)
{
dfs(y, x);
//daca y, care este fiu al lui x poate sa se intoarca mai sus decat x, actualizez nma[x]
// (x prin intermediul lui se va intoarce mai sus)
if(nma[x] > nma[y])
nma[x] = nma[y];
//determinare componente biconexe
if(nivel[x] <= nma[y])
bcx(x);
}
else //am dat de o muchie de intoarcere
{
//daca y, care este fiu al lui x se afla mai sus decat x(a fost deja vizitat) si nivelul sau este
// strict mai mic(e mai sus) decat nivelul la care se poate intoarce x, atunci actualizez nma[x]
// (x prin intermediul lui y, al muchiei de inoarcere, se va intoarce mai sus)
if(nma[x] > nivel[y])
nma[x] = nivel[y];
}
}
}
int main()
{
fin>>n>>m;
la.resize(n+1);
for(int i=0; i<m; ++i)
{
int x ,y;
fin >> x >> y;
la[x].push_back(y);
la[y].push_back(x);
}
dfs(1, 1);
fout << biconexe.size() << "\n";
for(int i=0; i<biconexe.size(); ++i)
{
for(int j=0; j<biconexe[i].size(); ++j)
fout << biconexe[i][j] << " ";
fout << "\n";
}
}