Pagini recente » Cod sursa (job #799008) | Cod sursa (job #2383172) | Cod sursa (job #801276) | Cod sursa (job #3155334) | Cod sursa (job #1169004)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int nr_noduri, nr_muchii;
vector<int> *v;
vector<vector<int>> componenta;
stack<int> s;
int *adancime, *lowpoint;
void DFS(int nod, int distanta)
{
int fii = 0;
lowpoint[nod] = adancime[nod] = distanta;
for (int i = 0; i < v[nod].size(); i++)
if (!adancime[v[nod][i]])
{
s.push(v[nod][i]);
fii++;
DFS(v[nod][i], distanta + 1);
if (lowpoint[v[nod][i]] < lowpoint[nod])
lowpoint[nod] = lowpoint[v[nod][i]];
if (lowpoint[v[nod][i]] >= adancime[nod])
{
componenta.emplace_back();
while (s.top() != v[nod][i])
{
componenta[componenta.size() - 1].push_back(s.top());
s.pop();
}
s.pop();
componenta[componenta.size() - 1].push_back(nod);
componenta[componenta.size() - 1].push_back(v[nod][i]);
}
}
else
if (adancime[v[nod][i]] < lowpoint[nod] && adancime[nod] - 1 != adancime[v[nod][i]])
lowpoint[nod] = adancime[v[nod][i]];
}
int main()
{
f >> nr_noduri >> nr_muchii;
v = new vector<int>[nr_noduri];
adancime = new int[nr_noduri];
lowpoint = new int[nr_noduri];
for (int i = 0; i < nr_noduri; i++)
adancime[i] = 0;
for (int i = 0; i < nr_muchii; i++)
{
int nod1, nod2;
f >> nod1 >> nod2;
v[nod1 - 1].push_back(nod2 - 1);
v[nod2 - 1].push_back(nod1 - 1);
}
DFS(0, 1);
g << componenta.size() << endl;
for (int i = 0; i < componenta.size(); i++)
{
for (int j = 0; j < componenta[i].size(); j++)
g << componenta[i][j] + 1 << ' ';
g << endl;
}
f.close();
g.close();
delete[] v;
delete[] adancime;
delete[] lowpoint;
return 0;
}