Pagini recente » Cod sursa (job #348811) | Cod sursa (job #3003220) | Cod sursa (job #2471904) | Cod sursa (job #2621854) | Cod sursa (job #2388185)
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,biconex;
vector< int > v[NMAX],sol[NMAX];
int fr[NMAX],dm[NMAX],niv[NMAX];
deque<int >q;
void dfs(int k, int tata)
{
niv[k]=niv[tata]+1;;
fr[k]=1;
q.push_back(k);
dm[k]=niv[k];
for(auto x : v[k])
{
if(x==tata)continue;
if(fr[x])
{
dm[k]=dm[k]<niv[x]? dm[k] : niv[x];
continue;
}
dfs(x,k);
dm[k]= dm[k] < dm[x] ? dm[k] : dm[x];
if(niv[k]<=dm[x])
{
++biconex;
int t;
do
{
t=q.back();
q.pop_back();
sol[biconex].push_back(t);
}while(!q.empty()&&t!=x);
sol[biconex].push_back(k);
}
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;++i)
{
int x,y;
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
fout<<biconex<<"\n";
for( int i=1;i<=biconex;++i, fout<<"\n")
for( auto x :sol[i])fout<<x<<" ";
return 0;
}