Pagini recente » Cod sursa (job #1099338) | Statistici Scinteie Alexandru Gabriel (GabrielScinteie) | Cod sursa (job #1520847) | Cod sursa (job #1986156) | Cod sursa (job #3041386)
#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], stck[N];
vector<int> v[N], afis[N];
void dfs(int start){
lv[start] = low[start] = level;
stck[t] = start;
t++;
for(int i=0; i<v[start].size(); i++){
int neig = v[start][i];
if(lv[neig] == 0){
level++;
parent[neig] = start;
dfs(neig);
low[start] = min(low[start], low[neig]);
if(low[neig] >= lv[start]){
t--;
while(stck[t] != start){
afis[nr_biconex].push_back(stck[t]);
t--;
}
afis[nr_biconex].push_back(start);
t++;
nr_biconex++;
}
}
else{
if(parent[neig] != start)
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=0; j<afis[i].size(); j++)
g<<afis[i][j]<<' ';
g<<'\n';
}
return 0;
}