Pagini recente » Cod sursa (job #1584256) | Cod sursa (job #3196341) | Cod sursa (job #142782) | Cod sursa (job #3204616) | Cod sursa (job #1650137)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
#define MAXN 100005
vector<int> graf[MAXN], rasp[MAXN];
stack<int> st;
int nivel[MAXN], low[MAXN];
int n,m,cbc;
void scoate(int nod, int urm)
{
while(st.top() != urm)
{
rasp[cbc].push_back( st.top() );
st.pop();
}
st.pop();
rasp[cbc].push_back(nod);
rasp[cbc].push_back(urm);
}
void dfs(int nod, int k)
{
nivel[nod]=low[nod]=k;
for(int i=0; i<graf[nod].size(); i++)
{
int urm = graf[nod][i];
if(!nivel[urm])
{
st.push(urm);
dfs(urm,k+1);
low[nod]=min(low[nod], low[urm]);
if(low[urm] >= nivel[nod])
{
cbc++;
scoate(nod,urm);
}
}
else
low[nod]=min(low[nod], nivel[urm]);
}
}
int main()
{
int n,m,i,j,x,y;
cin>>n>>m;
for(i=1; i<=m; i++)
{
cin>>x>>y;
graf[x].push_back(y);
}
st.push(1);
dfs(1,1);
cout<<cbc<<"\n";
for(i=1; i<=cbc; i++)
{
sort(rasp[i].begin(),rasp[i].end());
for(j=0; j<rasp[i].size(); j++)
cout<<rasp[i][j]<<" ";
cout<<"\n";
}
return 0;
}