Pagini recente » Cod sursa (job #1893461) | Cod sursa (job #2151782) | Cod sursa (job #2846001) | Cod sursa (job #2217388) | Cod sursa (job #3176011)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<vector<int>> ma;
stack<int> s;
vector<int> mini,desc; ///low mini dfn desc
int tot,timp=1;
vector<vector<int>> ra;
vector<int> v;
void dfs(int nod)
{
mini[nod]=timp;
desc[nod]=timp;
s.push(nod);
++timp;
vector<int>::iterator el;
for(el=ma[nod].begin();el!=ma[nod].end();++el)
{
if(desc[*el]==0)
{
dfs(*el);
mini[nod]=min(mini[nod],mini[*el]);
if(mini[*el]>=desc[nod])
{
int x;
++tot;
v.push_back(nod);
do{
x=s.top();
s.pop();
v.push_back(x);
}while(x!=*el);
ra.push_back(v);
v.clear();
}
}
else
mini[nod]=min(mini[nod],desc[*el]);
}
}
int main()
{
int n,m,x,y;
fin>>n>>m;
ma.resize(n+1);
mini.resize(n+1,0);
desc.resize(n+1,0);
for(int k=1;k<=m;k++)
{
fin>>x>>y;
ma[x].push_back(y);
ma[y].push_back(x);
}
dfs(1);
vector<int>::iterator el;
vector<vector<int>>::iterator k;
fout<<tot<<'\n';
for(k=ra.begin();k!=ra.end();k++)
{
for(el=k->begin();el!=k->end();el++)
fout<<*el<<" ";
fout<<'\n';
}
return 0;
}