Pagini recente » Cod sursa (job #2269743) | Cod sursa (job #700090) | Cod sursa (job #2247654) | Cod sursa (job #187839) | Cod sursa (job #2201314)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define Nmax 100000
using namespace std;
int idx;
vector<int> comp_biconexe[Nmax + 2];
stack<int> vf_comp_biconexe;
void citire(int &n, vector<int>* &la)
{
ifstream f("biconex.in");
int m, x, y;
f >> n >> m;
la = new vector<int>[n+1];
for(int i=1; i<=m; i++)
{
f >> x >> y;
la[x].push_back(y);
la[y].push_back(x);
}
f.close();
}
void DFS(const int& nod, const int& nod_vechi, vector<int>* la, bool* viz, int* nivel, int* nivel_min)
{
viz[nod] = true;
nivel[nod] = nivel[nod_vechi] + 1;
nivel_min[nod] = nivel[nod];
vf_comp_biconexe.push(nod);
for (int i = 0; i < (int) la[nod].size(); i++)
{
int nod_curent = la[nod][i];
if (!viz[nod_curent]) //daca e muchie de traversare
{
DFS(nod_curent, nod, la, viz, nivel, nivel_min);
nivel_min[nod] = min(nivel_min[nod], nivel_min[nod_curent]);
if (nivel[nod] <= nivel_min[nod_curent])
{
idx++;
while (vf_comp_biconexe.top() != nod_curent && !vf_comp_biconexe.empty())
{
comp_biconexe[idx].push_back(vf_comp_biconexe.top());
vf_comp_biconexe.pop();
}
comp_biconexe[idx].push_back(nod_curent);
if (!vf_comp_biconexe.empty())
vf_comp_biconexe.pop();
comp_biconexe[idx].push_back(nod);
}
}
else //daca e muchie de intoarcere
{
if (nod_curent != nod_vechi)
{
nivel_min[nod] = min(nivel_min[nod], nivel[nod_curent]);
}
}
}
}
int main()
{
int i, j, n;
vector <int> *la;
citire(n, la);
bool *viz = new bool[n+1]();
int *nivel = new int[n+1]();
int *nivel_min = new int[n+1]();
DFS(1, 0, la, viz, nivel, nivel_min);
ofstream fout("biconex.out");
fout << idx << '\n';
for (i = 1; i <= idx; i++)
{
for (j = 0; j < (int) comp_biconexe[i].size(); j++)
{
fout << comp_biconexe[i][j] << ' ';
}
fout << '\n';
}
fout.close();
return 0;
}