Pagini recente » Cod sursa (job #1204496) | Cod sursa (job #1298146) | Cod sursa (job #1902763) | Cod sursa (job #2039295) | Cod sursa (job #3152671)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
std::vector<std::vector<int>> V;
std::vector<int> dist, low, viz;
std::vector<std::unordered_set<int>> res;
std::stack<int> S;
int cnt;
void AP(int u, int parent, int time){
viz[u] = true;
dist[u] = low[u] = ++time;
int children = 0;
for(int v : V[u]){
if(!viz[v]){
++children; S.push(u);
AP(v, u, time);
low[u] = std::min(low[u], low[v]);
if(dist[u] == 1 || (dist[u] > 1 && dist[u] <= low[v])){
S.push(v);
std::unordered_set<int> values;
while(!S.empty() && S.top() != u){
values.insert(S.top());
S.pop();
}
if(!S.empty()){
values.insert(S.top());
S.pop();
}
res.push_back(values);
cnt ++;
}
}
else if(v != parent){
low[u] = std::min(low[u], dist[v]);
if(dist[v] < dist[u])
S.push(u);
}
}
}
void APutil(int n){
dist = low = viz = std::vector<int> (n + 1);
for(int i = 1; i <= n; i++){
if(!viz[i]){
AP(i, -1, 0);
}
}
if(!S.empty())
++cnt;
std::unordered_set<int> temp;
while(!S.empty()){
temp.insert(S.top());
S.pop();
}
res.push_back(temp);
fout << cnt << "\n";
for(int i = 0; i < res.size(); i++){
for(auto it : res[i])
fout << it << " ";
fout << "\n";
}
}
int main()
{
int n, m, x, y;
fin >> n >> m;
V = std::vector<std::vector<int>> (n + 1);
for(int i = 1; i <= m; i++){
fin >> x >> y;
V[x].push_back(y);
V[y].push_back(x);
}
APutil(n);
return 0;
}