Pagini recente » Borderou de evaluare (job #800521) | Borderou de evaluare (job #2325475) | Borderou de evaluare (job #1753267) | Borderou de evaluare (job #1047100) | Cod sursa (job #2165171)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int n,m,i,j,comp,t[100001],niv[100001],l[100001];
bool viz[100001];
vector <int> a[100001];
vector <vector <int> > sol;
stack <int> st;
void dfs(int k)
{
int it,x;
viz[k]=1;
niv[k]=niv[t[k]]+1;
l[k]=niv[k];
st.push(k);
for(it=0;it!=a[k].size();it++)
{
if(viz[a[k][it]])
{
if(a[k][it]!=t[k])
l[k]=min(l[k],niv[a[k][it]]);
continue;
}
t[a[k][it]]=k;
dfs(a[k][it]);
l[k]=min(l[k],l[a[k][it]]);
if(niv[k]<=l[a[k][it]])
{
sol.push_back(vector<int>(0));
do
{
x=st.top();
st.pop();
sol[comp].push_back(x);
}
while(x!=a[k][it]);
sol[comp].push_back(k);
comp++;
}
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
while(m)
{
scanf("%d%d",&i,&j);
a[i].push_back(j);
a[j].push_back(i);
m--;
}
for(i=1;i<=n;i++)
if(!viz[i])
{
t[i]=0;
dfs(i);
}
printf("%d\n",comp);
for(i=0;i<sol.size();i++,printf("\n"))
for(j=0;j<sol[i].size();j++)
printf("%d ",sol[i][j]);
return 0;
}