Pagini recente » Cod sursa (job #787554) | Cod sursa (job #1383285) | Cod sursa (job #319780) | Cod sursa (job #872181) | Cod sursa (job #2680183)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream in ("biconex.in");
ofstream out("biconex.out");
const int nmax=1e5;
struct edge{
int u, v;
};
vector <edge> stk;
bool viz[nmax+2];
int low[nmax+2], tin[nmax+2];
int n, m, x, y;
int mom;
vector <vector <int> > comp;
vector <int> muchii[nmax+2];
void dfs(int nod, int par){
viz[nod]=true;
tin[nod]=low[nod]=++mom;
int copii=0;
for(auto &x:muchii[nod]){
if(viz[x]==false){
stk.push_back({nod, x});
copii++;
dfs(x, nod);
if(low[x]>=tin[nod]){ ///adica nod e articulatie
comp.push_back(vector<int>());
while(!stk.empty()&&stk.back().u!=nod&&stk.back().v!=x){
comp.back().push_back(stk.back().v);
stk.pop_back();
}
comp.back().push_back(stk.back().v);
comp.back().push_back(stk.back().u);
stk.pop_back();
}
/*else if(par==0&&copii>1){
comp.push_back(vector<int>());
while(!stk.empty()&&stk.back().u!=nod&&stk.back().v!=x){
comp.back().push_back(stk.back().v);
stk.pop_back();
}
comp.back().push_back(stk.back().v);
comp.back().push_back(stk.back().u);
stk.pop_back();
}*/
low[nod]=min(low[nod], low[x]);
}
else if(x!=par)
low[nod]=min(low[nod], tin[x]);
}
// if(par==0&&!stk.empty()){
// comp.push_back(vector<int>());
// while(stk.size()>1){
// comp.back().push_back(stk.back().v);
// stk.pop_back();
// }
// comp.back().push_back(stk.back().v);
// comp.back().push_back(stk.back().u);
// stk.pop_back();
// }
}
ostream & operator <<(ostream & out, vector <int> & vec){
for(auto &x:vec)
out<<x<<" ";
return out;
}
int main()
{
in>>n>>m;
for(int i=1; i<=m; i++){
in>>x>>y;
muchii[x].push_back(y);
muchii[y].push_back(x);
}
dfs(1, 0);
out<<comp.size()<<"\n";
for(auto &x:comp)
out<<x<<"\n";
return 0;
}