Pagini recente » Cod sursa (job #544651) | Cod sursa (job #220641) | Cod sursa (job #326522) | Cod sursa (job #2550722) | Cod sursa (job #2299907)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector< vector< int > > G;
int n,m;
void citire(){
f>>n>>m;
G.resize(n+2);
for(int i=1,x,y;i<=m;i++){
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
vector<int> lvl(NMAX),low(NMAX);
int pasi,nrcomp;
stack< pair<int,int> > q;
vector<int> componente[NMAX];
void DFS(int node){
lvl[node] = low[node] = ++pasi;
for(auto it: G[node]){
if(!lvl[it]){
q.push(make_pair(node,it));
DFS(it);
low[node] = min(low[node], low[it]);
if(low[it]>=lvl[node]){
nrcomp++;
while(q.top().first!=node)
componente[nrcomp].push_back(q.top().second),
q.pop();
componente[nrcomp].push_back(q.top().first);
componente[nrcomp].push_back(q.top().second);
q.pop();
sort(componente[nrcomp].begin(),componente[nrcomp].end());
}
}
else low[node]=min(low[node],lvl[it]);
}
}
void afisare(){
g<<nrcomp<<"\n";
for(int i=1;i<=nrcomp;i++)
{for(auto it:componente[i])
g<<it<<" ";
g<<"\n";
}
}
int main()
{
citire();
for(int i=1;i<=n;i++)
if(!lvl[i])
DFS(i);
afisare();
return 0;
}