Pagini recente » Cod sursa (job #3146337) | Cod sursa (job #822126) | Cod sursa (job #3133865) | Cod sursa (job #880577) | Cod sursa (job #2515248)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5 + 1;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N, M;
vector<vector<int>> graph(NMAX, vector<int>());
int low[NMAX], id[NMAX], timer = 0;
stack<int> stivaNoduri;
vector<vector<int>> bcs;
void DFS(int nod, int tata)
{
id[nod] = low[nod] = ++timer;
stivaNoduri.push(nod);
for(auto& fiu : graph[nod])
{
if(fiu == tata) continue;
if(id[fiu] != 0)
{
low[nod] = min(low[nod], id[fiu]);
}
else
{
DFS(fiu, nod);
low[nod] = min(low[fiu], low[nod]);
if(id[nod] <= low[fiu])
{
bcs.push_back(vector<int>());
int varf;
do
{
varf = stivaNoduri.top();
bcs.back().push_back(varf);
stivaNoduri.pop();
}while(varf != fiu);
bcs.back().push_back(nod);
}
}
}
}
int main()
{
fin >> N >> M;
for(int i = 1; i <= M; ++i)
{
int x, y;
fin >> x >>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
DFS(1, -1);
fout << bcs.size() << '\n';
for(vector<int>& bc : bcs)
{
for(int nod : bc)
{
fout << nod << ' ';
}
fout << '\n';
}
}