Pagini recente » Cod sursa (job #1737316) | Cod sursa (job #2213124) | Cod sursa (job #1264149) | Cod sursa (job #1783770) | Cod sursa (job #1666624)
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <stack>
using namespace std;
class dfs_class{
const int n;
const vector<vector<int>>& graf;
vector<vector<int>>& comps;
stack<int> st;
vector<bool> viz;
vector<int> adanc, highest_vec;
public:
dfs_class(const vector<vector<int>>& g, vector<vector<int>>& r):
n(g.size()), graf(g), comps(r), viz(n, false), adanc(n, 0), highest_vec(n, 0){}
void operator()(const int cur = 0, const int prev = -1){
viz[cur] = true;
highest_vec[cur] = adanc[cur];
for(const auto next : graf[cur]){
if(next == prev){
continue;
}
else if(!viz[next]){
adanc[next] = adanc[cur] + 1;
st.push(next);
(*this)(next, cur);
highest_vec[cur] = min(highest_vec[cur], highest_vec[next]);
if(highest_vec[next] >= adanc[cur]){
comps.emplace_back(1, cur);
while(st.top() != next){
comps.back().push_back(st.top());
st.pop();
}
comps.back().push_back(st.top());
st.pop();
}
}
else{
highest_vec[cur] = min(highest_vec[cur], adanc[next]);
}
}
}
};
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
f >> n >> m;
vector<vector<int>> graf(n);
for(int i = 0, a, b; i < m; ++i){
f >> a >> b;
--a, --b;
graf[a].push_back(b);
graf[b].push_back(a);
}
vector<vector<int>> comps;
dfs_class(graf, comps)();
g << comps.size() << '\n';
for(const auto& x : comps){
for(const auto y : x){
g << y+1 << ' ';
}
g << '\n';
}
return 0;
}