Pagini recente » Cod sursa (job #2636243) | Cod sursa (job #25312) | Cod sursa (job #116551) | Cod sursa (job #2627394) | Cod sursa (job #1136209)
#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#include <set>
using namespace std;
#define MAXN 100005
#define pb push_back
vector<int> graf[MAXN];
int h[MAXN];
int low[MAXN];
bitset<MAXN> viz;
stack<pair<int,int> > stiva;
vector<set<int> > comp;
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();
comp.push_back(nou);
}
void dfs(int nod,int father)
{
low[nod]=h[nod];
vector<int>::iterator it;
for(it=graf[nod].begin();it!=graf[nod].end();it++)
if(!viz[*it])
{
viz[*it]=1;
h[*it]=h[nod]+1;
stiva.push(make_pair(nod,*it));
dfs(*it,nod);
low[nod]=min(low[nod],low[*it]);
if(h[nod]<=low[*it])
scoate(nod,*it);
}
else if(*it!=father)
low[nod]=min(low[nod],h[*it]);
}
int main()
{
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n=0,m=0,i,a,b;
cin>>n>>m;
for(i=0;i<m;i++)
{
cin>>a>>b;
graf[a].pb(b);
graf[b].pb(a);
}
for(i=1;i<=n;i++)
if(!viz[i])
{
h[i]=1;
viz[i]=1;
dfs(i,0);
}
vector<set<int> >::iterator it;
set<int>::iterator it2;
cout<<comp.size()<<'\n';
for(it=comp.begin();it!=comp.end();it++)
{
for(it2=it->begin();it2!=it->end();it2++)
cout<<*it2<<' ';
cout<<'\n';
}
cin.close();
cout.close();
return 0;
}