Pagini recente » Cod sursa (job #458884) | Cod sursa (job #427259) | Cod sursa (job #129333) | Cod sursa (job #678343) | Cod sursa (job #2372489)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int indexx = 0;
vector<vector<int>> graph;
vector<int> low;
vector<int> level;
stack<int> Stack;
vector<bool> vizitat;
vector<vector<int>> components;
void biconex(int node){
level.at(node) = low.at(node) = ++indexx;
Stack.push(node);
vizitat.at(node) = true;
for(auto& kid:graph.at(node)){
if(vizitat.at(kid)){
low.at(node) = min(low.at(node), level.at(kid));
continue;
}
biconex(kid);
low.at(node) = min(low.at(kid), low.at(node));
if(low.at(kid)>=level.at(node)){
Stack.push(node);
vector<int> component;
int x = Stack.top();
do {
Stack.pop();
component.push_back(x);
x = Stack.top();
} while(x!=node);
components.push_back(component);
}
}
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin>>n>>m;
graph.resize(n+1, vector<int>());
int x, y;
for(int i=1; i<=m; i++){
fin>>x>>y;
graph.at(x).push_back(y);
graph.at(y).push_back(x);
}
low.resize(n+1);
level.resize(n+1);
vizitat.resize(n+1, false);
biconex(1);
fout<<components.size()<<endl;
for(auto& component:components){
for(auto& element:component) fout<<element<<" ";
fout<<endl;
}
}