Pagini recente » Cod sursa (job #2800185) | Cod sursa (job #1957217) | Cod sursa (job #221084) | Cod sursa (job #3238936) | Cod sursa (job #2680034)
#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;
int n, m, x, y;
vector <int> muchii[nmax+2];
bool viz[nmax+2];
int momIn[nmax+2];
int low[nmax+2];
int mom=0;
vector <vector <int> > comp;
vector <int> stk;
void dfs(int nod, int par){
viz[nod]=true;
low[nod]=momIn[nod]=++mom;
stk.push_back(nod);
for(auto &x:muchii[nod]){
if(viz[x]==false){
dfs(x, nod);
low[nod]=min(low[x], low[nod]);
if(low[x]>=momIn[nod]){ ///adica ultimul accesibil e nodul actual
comp.push_back(vector<int>());
while(stk.back()!=nod){
comp.back().push_back(stk.back());
stk.pop_back();
}
comp.back().push_back(nod);
}
}
else { ///deci a fost vizitat
low[nod]=min(low[nod], momIn[x]);
}
}
if(low[nod]==momIn[nod]&&par!=0){ ///adica e radacina
comp.push_back(vector<int>());
while(!stk.empty()){
comp.back().push_back(stk.back());
stk.pop_back();
}
}
}
ostream & operator <<(ostream & out, vector <int> & vec){
sort(vec.begin(), vec.end());
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);
}
for(int i=1; i<=n; i++){
if(viz[i]==false)
dfs(i, 0);
}
out<<comp.size()<<"\n";
for(auto &x:comp)
out<<x<<"\n";
return 0;
}