Pagini recente » Cod sursa (job #3346712) | Cod sursa (job #3311945) | Cod sursa (job #3262906) | Cod sursa (job #474016) | Cod sursa (job #3345555)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#define NMAX 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N,M,nrb;
int nivel[NMAX],low[NMAX];
vector<int> graph[NMAX];
stack<pair<int,int>> stiva;
set<int> comp[NMAX];
void citire()
{
fin>>N>>M;
int u,v;
for(int i=1; i<=M; i++)
{
fin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
}
}
void DFS(int parent, int nod)
{
nivel[nod]=nivel[parent]+1;
low[nod]=nivel[nod];
for(int i=0; i<graph[nod].size(); i++)
{
int next_nod=graph[nod][i];
if(next_nod==parent)
{
continue;
}
if(nivel[next_nod])
{
low[nod]=min(low[nod],nivel[next_nod]);
}
else
{
stiva.push({nod,next_nod});
DFS(nod,next_nod);
low[nod]=min(low[nod],low[next_nod]);
if(low[next_nod]>=nivel[nod])
{
nrb++;
while(!stiva.empty())
{
comp[nrb].insert(stiva.top().first);
comp[nrb].insert(stiva.top().second);
if(stiva.top().first==nod && stiva.top().second==next_nod)
{
stiva.pop();
break;
}
stiva.pop();
}
}
}
}
}
int main()
{
citire();
nrb=0;
DFS(0,1);
fout<< nrb << "\n";
for(int i=1; i<=nrb; i++)
{
for(auto j:comp[i])
{
fout<< j << " ";
}
fout<< "\n";
}
return 0;
}