Pagini recente » Cod sursa (job #767812) | Cod sursa (job #358510) | Cod sursa (job #2305382) | Cod sursa (job #1770555) | Cod sursa (job #2660541)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
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];
stack <pair <int, int>> graph_search;
vector <vector <pair <int, 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];
for (int i = 0; i < lv[node].size(); i++){
int next_node = lv[node][i];
pair <int, int> edge(node, next_node);
if (!visited[next_node]){
n_children += 1;
graph_search.push(edge);
///cout << "added " << edge.first << " " << edge.second << " | ";
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 && n_children > 1)){ ///cazul cand descopar un nod de articulatie
biconnected_components.resize(biconnected_components.size() + 1);
while (graph_search.top() != edge){
///cout << "popped " << graph_search.top().first << " " << graph_search.top().second << " | ";
biconnected_components[biconnected_components.size() - 1].push_back(graph_search.top());
graph_search.pop();
}
///cout << "popped " << graph_search.top().first << " " << graph_search.top().second << " | ";
biconnected_components[biconnected_components.size() - 1].push_back(graph_search.top());
graph_search.pop();
}
}
else if(next_node != parent && low_level[node] > level[next_node]){ /// tratez cazul cand exista o muchie de intoarcere
low_level[node] = level[next_node];
///cout << "added " << edge.first << " " << edge.second << " | ";
graph_search.push(edge); /// adaug si muchiile de intoarcere
}
}
}
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]){
DFS(i, -1);
if(!graph_search.empty()){
biconnected_components.resize(biconnected_components.size() + 1);
while(!graph_search.empty()){
biconnected_components[biconnected_components.size() - 1].push_back(graph_search.top());
graph_search.pop();
}
}
}
}
g << biconnected_components.size() << '\n';
for(int i = 0; i < biconnected_components.size(); i++){
set <int> shown;
for(int j = 0; j < biconnected_components[i].size(); j++){
int n1 = biconnected_components[i][j].first;
int n2 = biconnected_components[i][j].second;
if(shown.find(n1) == shown.end() ){
g << n1 << " ";
shown.insert(n1);
}
if(shown.find(n2) == shown.end() ){
g << n2 << " ";
shown.insert(n2);
}
///g << biconnected_components[i][j].first << " " << biconnected_components[i][j].second << " | ";
}
g << '\n';
}
return 0;
}