Pagini recente » Cod sursa (job #1078016) | Cod sursa (job #861233) | Cod sursa (job #1407461) | Cod sursa (job #1786126) | Cod sursa (job #1758237)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define NMAX 100001
struct Nod
{
int timp;
int low;
vector<int> vecini;
};
Nod noduri[NMAX];
vector< pair<int, int> > stiva;
vector< vector<int> > componente;
int timp = 0;
void aflaComponente(int nod);
void adaugaComponenta(int a, int b);
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
fin >> n >> m;
while (m--) {
int x, y;
fin >> x >> y;
noduri[x].vecini.push_back(y);
noduri[y].vecini.push_back(x);
}
aflaComponente(1);
fout << componente.size() << "\n";
for (auto comp : componente) {
for (int nod : comp)
fout << nod << " ";
fout << "\n";
}
return 0;
}
void aflaComponente(int nod)
{
noduri[nod].timp = noduri[nod].low = ++timp;
for (int v : noduri[nod].vecini) {
if (noduri[v].timp <= 0) {
stiva.push_back({nod, v});
aflaComponente(v);
noduri[nod].low = min(noduri[nod].low, noduri[v].low);
if (noduri[v].low >= noduri[nod].timp) {
adaugaComponenta(nod, v);
}
}
else {
noduri[nod].low = min(noduri[nod].low, noduri[v].timp);
}
}
}
void adaugaComponenta(int a, int b)
{
vector<int> comp;
while (stiva.back().first != a) {
comp.push_back(stiva.back().second);
stiva.pop_back();
}
comp.push_back(stiva.back().second);
comp.push_back(stiva.back().first);
stiva.pop_back();
componente.push_back(comp);
}