Pagini recente » Cod sursa (job #1157198) | Cod sursa (job #3226253) | Cod sursa (job #2215634) | Cod sursa (job #2719082) | Cod sursa (job #2663939)
#include <bits/stdc++.h>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
int n, m;
std::vector<int> nei[100001], rank, low;
std::stack <std::pair <int, int>> search;
std::vector<std::vector<int>> comp;
void addBiconnectedComp(int x, int node){ //eliminam muchiile din stiva si adaugam componenta biconexa
std::vector<int> aux;
int aux1 = search.top().first;
int aux2 = search.top().second;
search.pop();
aux.push_back(aux1);
aux.push_back(aux2);
while(aux1 != x && aux2 != node){
aux1 = search.top().first;
aux2 = search.top().second;
search.pop();
if(find(aux.begin(), aux.end(), aux1) == aux.end())
aux.push_back(aux1);
if(find(aux.begin(), aux.end(), aux2) == aux.end())
aux.push_back(aux2);
}
comp.push_back(aux);
}
void dfs(int x, int parent, int step)
{
rank[x] = step;
low[x] = step;
for(auto node: nei[x]){ // parcurgem vecinii
if(rank[node] == -1){ //nevizitat
search.push(std::make_pair(x, node));
dfs(node, x, step + 1);
low[x] = std::min(low[x], low[node]); //actualizam low-> x poate ajunge mai sus folosind orice muchie de intoarcere a copiilor
if(low[node] >= rank[x])// x e punct de articulatie => eliminam toate muchiile din stiva si actualizam comp
addBiconnectedComp(x, node);
}
else{ //nodul e deja vizitat, deci e muchie de intoarcere
low[x] = std::min(low[x], rank[node]);
}
}
}
int main()
{
int x, y, i;
fin >> n >> m;
rank.resize(n + 1, -1); // rank[i] = al catelea nod a fost i in parcurgerea dfs
low.resize(n + 1); // low[i] =
for(i = 0; i < m; i++){
fin >> x >> y;
nei[x].push_back(y);
nei[y].push_back(x);
}
dfs(1, 0, 0);
fout << comp.size() << '\n';
for(auto i: comp){
sort(i.begin(), i.end());
for(auto j: i)
fout << j << " ";
fout << '\n';
}
return 0;
}