Pagini recente » Cod sursa (job #669921) | Cod sursa (job #2290462) | Cod sursa (job #2123894) | Cod sursa (job #2607074) | Cod sursa (job #2698951)
#include <fstream>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
int index[NMAX], lowlink[NMAX];
int viz[NMAX], idx=1;
int nr_componente;
vector<int>graph[NMAX];
vector<vector<int>> sol;
stack<pair<int, int>>S; // nodurile
void citire(){
f>>n>>m;
int x, y;
for(int i=0; i<m; i++){
f>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
}
void biconex(int nod, int parent){
index[nod] = idx;
lowlink[nod] = idx;
idx++;
viz[nod] = 1;
for(auto &v:graph[nod]){
if(v == parent)
continue;
if(viz[v] == 0){
S.push({nod, v});
biconex(v, nod);
lowlink[nod] = min(lowlink[v], lowlink[nod]);
if(lowlink[v] >= index[nod]){
pair<int, int> el;
vector<int> temp;
do{
el = S.top();
temp.push_back(el.first);
temp.push_back(el.second);
S.pop();
}while(el.first != nod && el.second != v);
sort(temp.begin(), temp.end());
temp.erase(unique(temp.begin(), temp.end()), temp.end());
sol.push_back(temp);
}
}
else{
lowlink[nod] = min(lowlink[v], lowlink[nod]);
}
}
}
void parcurgere(){
biconex(1, 0);
}
void afisare(){
g<<sol.size()<<'\n';
for(auto &c:sol){
for(auto v: c)
g<<v<<' ';
g<<'\n';
}
}
int main()
{
citire();
parcurgere();
/**for(int i=1; i<=n; i++){
cout<<lowlink[i]<<' ';
}**/
afisare();
return 0;
}