Pagini recente » Cod sursa (job #2936196) | Cod sursa (job #2439274) | Cod sursa (job #1792112) | Cod sursa (job #1307575) | Cod sursa (job #2798041)
#include<bits/stdc++.h>
using namespace std;
ifstream in ("biconex.in");
ofstream out ("biconex.out");
vector<int> la[100005]; ///lista de adiacenta
vector <set <int>> componente;
//stack <int>s;
stack<pair<int, int>> stivaCB;
int minim[100005]; ///nivelul minim in care putem ajunge din nodul urent in subtree ul curent
bool vizitat[100005]; ///vectorul de vizitat ( 0 -neviz , 1- viz)
int discovery[100005]; ///primul moment in care trecem prin nod in dfs
static int moment = 1; ///contorizam momentul de trecere prin noduri
void dfsbiconex(int nod_curent, int nod_precedent)
{
discovery[nod_curent] = moment;
minim[nod_curent] = moment;
vizitat[nod_curent] = true;
moment++;
for(int i=0 ; i < la[nod_curent].size() ; i++)
{
int nod_adiacent = la[nod_curent][i];
// if (nod_adiacent != nod_precedent)
// {
if (vizitat[nod_adiacent] == false)
{
stivaCB.push(make_pair(nod_curent, nod_adiacent)); ///punem muchia curenta in stiva
dfsbiconex(nod_adiacent, nod_curent); ///continuam dfs
if (minim[nod_curent] > minim[nod_adiacent]) /// daca nodul adiacent face parte din acelasi subtree cu nodul curent
minim[nod_curent] = minim[nod_adiacent]; ///at. momentul minim la care putem ajunge din el e acelasi cu momentul minim in care ajungem din nodul curent
if (minim[nod_adiacent] >= discovery[nod_curent]) ///comp. biconexa (pt. ca mom. min coresp. nodului adiacent este mai mare sau = cu prima data cand trecem prin nodul curent in dfs
{
set<int> noduri_cb; ///setul cu nodurile din componenta biconexa
int nod1, nod2;
do
{
nod1 = stivaCB.top().first;
nod2 = stivaCB.top().second;
noduri_cb.insert(nod1);
noduri_cb.insert(nod2);
stivaCB.pop();
}
while (nod1 != nod_curent || nod2 != nod_adiacent); ///nu am gasit un element care se repeta
componente.push_back(noduri_cb);
}
}
else ///nodul curent a fost vizitat
{
if (minim[nod_curent] > discovery[nod_adiacent]) ///avem muchie de intoarcere de la nodul adiacent la nodul curent(am trecut deja prin nodul adiacent)
{
minim[nod_curent] = discovery[nod_adiacent]; ///minimul se actualizeaza cu momentul in care am dat de nodul adiacent deja vizitat
}
}
// }
}
}
int main()
{
int n,m;
in>>n>>m; ///citim nr noduri + nr muchii
for(int i=1; i<=m; i++)
{
int a,b;
in>>a>>b;
///graf neorientat
la[a].push_back(b);
la[b].push_back(a);
}
dfsbiconex(1, 0);
out<< componente.size() <<'\n';
set<int>::iterator it;
for (auto &i: componente)
{
for (it = i.begin(); it != i.end(); it++)
{
out << *it << " ";
}
out << "\n";
}
return 0;
}