Pagini recente » Cod sursa (job #1387246) | Cod sursa (job #78288) | Cod sursa (job #1604739) | Cod sursa (job #616262) | Cod sursa (job #3256261)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> v[100005],aux;
vector<vector<int>> compb;
int y,parent[100005],disc[100005],low[100005],viz[100005];
void tarjan(int x)
{
viz[x]=1;
disc[x]=low[x]=++y;
int children=0;
aux.push_back(x);
for(auto i:v[x])
if(i!=parent[x]){
if(viz[i])
low[x]=min(low[x],disc[i]);
else
{
parent[i]=x;
if(!parent[x])
children++;
tarjan(i);
low[x]=min(low[x],low[i]);
if((parent[i]&&low[i]>=disc[x])||(!parent[x]&&children>1))
{
compb.push_back(vector<int>());
while(aux.back()!=x)
{
compb.back().push_back(aux.back());
aux.pop_back();
}
compb.back().push_back(x);
}
}}
}
int main()
{
int n,m;
f>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
f>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
for(int i=1;i<=n;i++)
if(!viz[i])
{
tarjan(i);
if(!aux.empty())
//compb.push_back(aux);
aux.clear();
}
g<<compb.size();
for(auto i:compb)
{
g<<'\n';
for(auto j:i)
g<<j<<" ";
}
return 0;
}