Pagini recente » Rating Pascale Radu-Ioan (pasquale) | Cod sursa (job #972680) | Cod sursa (job #615419) | Cod sursa (job #391172) | Cod sursa (job #2022015)
#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 fth = 0)
{
father[current] = fth;
noduri.push(current);
lowPoint[current] = nivel[current] = nivel[fth] + 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(father[noduri.top()] != current)
{
t = noduri.top();
noduri.pop();
ret.back().push_back(t);
}
ret.back().push_back(noduri.top());
noduri.pop();
ret.back().push_back(current);
}
}
}
}
private:
stack<int> noduri;
int nivel[nMax];
int lowPoint[nMax];
int father[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;
}