Pagini recente » Cod sursa (job #1670238) | Cod sursa (job #571167) | Cod sursa (job #2402973) | Cod sursa (job #2108836) | Cod sursa (job #2557119)
#include<fstream>
#include<iostream>
#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);
for(auto& neighbor: G[x])
{
if(!viz[neighbor])
{
tarjan(neighbor, x);
M[x][1] = min(M[x][1], M[neighbor][1]);
if(M[x][0] <= M[neighbor][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;
cin >> N >> M;
for(int i=1;i<=M;++i)
{
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
tarjan(1, 0);
cout << components.size() <<"\n";
for(auto& comp:components)
{
for(auto& node:comp)
{
cout << node <<" ";
}
cout<<"\n";
}
return 0;
}