Pagini recente » Cod sursa (job #1255532) | Cod sursa (job #2813041) | Cod sursa (job #2611028) | Cod sursa (job #1345052) | Cod sursa (job #3041415)
#include <fstream>
#include <vector>
#define N 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,level=1, nr_biconex, t;
int lv[N], low[N], parent[N];
struct edge{
int x, y;
}stck[200005];
vector<int> v[N], afis[N];
void dfs(int start){
lv[start] = low[start] = level;
for(int i=0; i<v[start].size(); i++){
int neig = v[start][i];
if(lv[neig] == 0){
level++;
parent[neig] = start;
stck[t] = {start, neig};
t++;
dfs(neig);
low[start] = min(low[start], low[neig]);
if(low[neig] >= lv[start]){
t--;
while(stck[t].x != start){
afis[nr_biconex].push_back(stck[t].y);
t--;
}
afis[nr_biconex].push_back(stck[t].y);
afis[nr_biconex].push_back(stck[t].x);
nr_biconex++;
}
}
else{
if(parent[start] != neig)
low[start] = min(low[start], lv[neig]);
}
}
}
int main()
{
f>>n>>m;
int x,y;
for(int i=0; i<m; i++){
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1);
g<<nr_biconex<<'\n';
for(int i=0; i<nr_biconex; i++){
for(int j=afis[i].size()-1; j>=0; j--)
g<<afis[i][j]<<' ';
g<<'\n';
}
return 0;
}