Pagini recente » Cod sursa (job #491123) | Cod sursa (job #1493931) | Cod sursa (job #1032370) | Cod sursa (job #671752) | Cod sursa (job #1252028)
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#include <utility>
#include <set>
#define NMAX 100005
using namespace std;
vector<int> graf[NMAX];
int h[NMAX];
int low[NMAX];
bitset<NMAX> viz;
stack<pair<int,int> > stiva;
vector<set<int> > Set;
void scoate(int x,int y){
set<int> nou;
while(!stiva.empty() && (stiva.top().first!=x || stiva.top().second!=y)){
nou.insert(stiva.top().first);
nou.insert(stiva.top().second);
stiva.pop();
}
nou.insert(stiva.top().first);
nou.insert(stiva.top().second);
stiva.pop();
Set.push_back(nou);
}
void dfs(int nod,int father){
viz[nod]=1;
h[nod]=h[father]+1;
low[nod]=h[nod];
for(vector<int>::iterator it=graf[nod].begin();it!=graf[nod].end();it++)
if(!viz[*it]){
stiva.push(make_pair(nod,*it));
dfs(*it,nod);
low[nod]=min(low[nod],low[*it]);
if(low[*it]>=h[nod])
scoate(nod,*it);
}
else if(*it!=father)
low[nod]=min(low[nod],low[*it]);
}
int main()
{
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n=0,m=0;
cin>>n>>m;
int a=0,b=0;
while(m--){
cin>>a>>b;
graf[a].push_back(b);
graf[b].push_back(a);
}
for(int i=1;i<=n;i++)
if(!viz[i])
dfs(i,0);
vector<set<int> >::iterator it;
set<int>::iterator it2;
cout<<Set.size()<<'\n';
for(it=Set.begin();it!=Set.end();it++){
cout<<*it->begin();
it2=it->begin();it2++;
for(;it2!=it->end();it2++)
cout<<' '<<*it2;
cout<<'\n';
}
cin.close();
cout.close();
return 0;
}