Pagini recente » Borderou de evaluare (job #759170) | Borderou de evaluare (job #2952963) | Cod sursa (job #2950554) | Cod sursa (job #2022009)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int nMax = 100005;
class graf
{
public:
vector<int> vecini[nMax];
void AddEdge(int x, int y)
{
vecini[x].push_back(y);
vecini[y].push_back(x);
}
void GetBiComp(vector<vector<int> > &ret, int current = 1, int father = 0)
{
noduri.push(current);
lowPoint[current] = nivel[current] = nivel[father] + 1;
for(auto v:vecini[current])
{
if(nivel[v])
lowPoint[current] = min(lowPoint[current], nivel[v]);
else
{
GetBiComp(ret, v, current);
lowPoint[current] = min(lowPoint[current], lowPoint[v]);
if(lowPoint[v] == nivel[current])
{
ret.resize(ret.size() + 1);
int t;
while(noduri.top() != current)
{
t = noduri.top();
noduri.pop();
ret.back().push_back(t);
}
ret.back().push_back(current);
}
}
}
}
private:
stack<int> noduri;
int nivel[nMax];
int lowPoint[nMax];
};
int n, m;
graf g;
vector<vector<int> > rasp;
void citire()
{
ifstream in("biconex.in");
in >> n >> m;
int x, y;
for(int i = 1; i <= m; ++i)
{
in >> x >> y;
g.AddEdge(x, y);
}
in.close();
}
void afisare()
{
ofstream out("biconex.out");
out << rasp.size() << "\n";
for(int i = 0; i < rasp.size(); ++i)
{
for(auto x:rasp[i])
out << x << " ";
out << "\n";
}
out.close();
}
int main()
{
citire();
g.GetBiComp(rasp);
afisare();
return 0;
}