Pagini recente » Cod sursa (job #478803) | Cod sursa (job #1634681) | Cod sursa (job #811561) | Cod sursa (job #916224) | Cod sursa (job #2660341)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
vector <int> lv[100005];
int visited[100005];
int level[100005];
int low_level[100005];
set <int> articulation_points;
stack <int> graph_search;
vector <vector <int>> biconnected_components;
void DFS(int node, int parent){
int n_children = 0;
level[node] = level[parent] + 1;
visited[node] = 1;
low_level[node] = level[node];
graph_search.push(node);
for (int i = 0; i < lv[node].size(); i++){
int next_node = lv[node][i];
if (!visited[next_node]){
n_children += 1;
DFS(next_node, node);
low_level[node] = min(low_level[node], low_level[next_node]); /// tratez cazul cand unul din nodurile din subarborele fiului are o muchie de intoarcere
if ((low_level[next_node] >= level[node] && parent != -1) || (parent == -1 && lv[node].size() > 1)){
biconnected_components.resize(biconnected_components.size() + 1);
while (graph_search.top() != node){
biconnected_components[biconnected_components.size() - 1].push_back(graph_search.top());
graph_search.pop();
}
biconnected_components[biconnected_components.size() - 1].push_back(graph_search.top());
}
}
else if(next_node != parent){ /// tratez cazul cand exista o muchie de intoarcere
low_level[node] = min(level[next_node], low_level[node]);
}
}
}
int main(){
f >> n >> m;
int x, y;
for(int i = 0; i < m; i++){
f >> x >> y;
lv[x].push_back(y);
lv[y].push_back(x);
}
/*for(int i = 1; i <= n; i++){
cout << i << ": ";
for (int j = 0; j < lv[i].size(); j++)
cout << lv[i][j] << " ";
cout << '\n';
}*/
for(int i = 1; i <= n; i++){
if (!visited[i]){
while (!graph_search.empty())
graph_search.pop();
DFS(i, -1);
}
}
g << biconnected_components.size() << '\n';
for(int i = 0; i < biconnected_components.size(); i++){
for(int j = 0; j < biconnected_components[i].size(); j++){
g << biconnected_components[i][j] << " ";
}
g << '\n';
}
return 0;
}