Pagini recente » Cod sursa (job #180760) | Cod sursa (job #2536548) | Cod sursa (job #2951450) | Cod sursa (job #2604189) | Cod sursa (job #2699595)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5+5;
vector <int> w[NMAX];
int nivel[NMAX], nivmin[NMAX];
stack < pair <int, int> > stiva;
vector < vector <int> > sol;
void retin(int a, int b){
pair <int, int> aux, stop;
stop = {a, b};
vector <int> vec;
while(true){
aux = stiva.top();
stiva.pop();
vec.push_back(aux.first);
vec.push_back(aux.second);
if(aux == stop)
break;
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
sol.push_back(vec);
}
void DFS(int nod, int t){
nivmin[nod] = nivel[nod] = nivel[t] + 1;
int nrel = w[nod].size();
for(int i = 0; i < nrel; ++i){
int vecin = w[nod][i];
if(vecin == t)
continue;
if(!nivel[vecin]){
stiva.push({nod, vecin});
DFS(vecin, nod);
nivmin[nod] = min(nivmin[nod], nivmin[vecin]);
if(nivmin[vecin] >= nivel[nod])
retin(nod, vecin);
}
else nivmin[nod] = min(nivmin[nod], nivel[vecin]);
}
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, i;
fin >> n >> m ;
for(i = 1; i <= m; ++i){
int a, b;
fin >> a >> b;
w[a].push_back(b);
w[b].push_back(a);
}
DFS(1, 0);
int nrsol = sol.size();
fout << nrsol << '\n';
for(i = 0; i < nrsol; ++i){
int nrel = sol[i].size();
for(int j = 0; j < nrel; ++j){
fout << sol[i][j] << ' ';
}
fout << '\n';
}
return 0;
}