Pagini recente » Cod sursa (job #1473609) | Cod sursa (job #264762) | Cod sursa (job #1099750) | Cod sursa (job #971001) | Cod sursa (job #1418410)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
#define Ndim 100005
int N,M;
vector<int> v[Ndim];
int low[Ndim];
int lvl[Ndim];
int ST[Ndim];
bool seen[Ndim];
vector< vector<int> > Sol;
int dfs(int s,int father)
{
ST[++ST[0]] = s;
low[s] = lvl[s];
seen[s] = true;
for(auto p: v[s]){
if(p == father) continue;
if(!seen[p]){
lvl[p] = lvl[s] + 1;
dfs(p,s);
low[s] = min(low[s],low[p]);
if(low[p] >= lvl[s]){
Sol.push_back(vector<int>());
int u = ST[ST[0]--];
Sol.back().push_back(u);
while(u != p){
u = ST[ST[0]--];
Sol.back().push_back(u);
}
Sol.back().push_back(s);
}
}
else if(lvl[p] < lvl[s]) // back edge
low[s] = min(low[s],lvl[p]);
}
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
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);
}
for(int i = 1; i <= N; i++)
if(!seen[i])
dfs(i,0);
fout << Sol.size() << "\n";
for(auto p: Sol){
for(auto j: p)
fout << j << " ";
fout << "\n";
}
}