Pagini recente » Cod sursa (job #667679) | Cod sursa (job #2973033) | Cod sursa (job #2092237) | Cod sursa (job #162234) | Cod sursa (job #2557050)
#include<fstream>
#include<vector>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<vector<int> > components;
vector<int> G[100010];
int M[100010][2];
int viz[100010];
int nr = 0;
vector<int> stack;
void tarjan(int x, int f)
{
++nr;
viz[x] = 1;
M[x][0] = M[x][1] = nr;
stack.push_back(x);
int mn = nr;
for(auto& neighbor: G[x])
{
if(!viz[neighbor])
{
tarjan(neighbor, x);
M[x][1] = min(M[x][1], M[neighbor][1]);
mn = min(mn, M[x][1]);
if(M[x][0] == M[x][1])
{
vector<int> comp;
while(stack.back() != x)
{
comp.push_back(stack.back());
stack.pop_back();
}
comp.push_back(x);
components.push_back(comp);
}
}
else if(neighbor != f)
{
M[x][1] = min(M[x][1], M[neighbor][1]);
}
}
}
int main()
{
int N,M;
in >> N >> M;
for(int i=1;i<=M;++i)
{
int x, y;
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
tarjan(1, 0);
out << components.size() <<"\n";
for(auto& comp:components)
{
for(auto& node:comp)
{
out << node <<" ";
}
out<<"\n";
}
return 0;
}