Pagini recente » Cod sursa (job #2483371) | Cod sursa (job #2810825) | Cod sursa (job #1455852) | Cod sursa (job #338799) | Cod sursa (job #1882512)
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1e5 + 10;
vector<int> vec[maxn] = {};
int t0[maxn] = {}, seen_t0[maxn] = {};
void dfs(const int cur, const int prev, const int cur_t = 1){
seen_t0[cur] = t0[cur] = cur_t;
for(const auto next : vec[cur]){
if(next == prev) continue;
else if(t0[next]) seen_t0[cur] = min(seen_t0[cur], t0[next]);
else dfs(next, cur, cur_t+1), seen_t0[cur] = min(seen_t0[cur], seen_t0[next]); } }
vector<vector<int>> comps;
void dfs_(const int cur, const int cur_comp){
for(const auto next : vec[cur]){
if(t0[next] != t0[cur]+1) continue;
else if(t0[cur] > seen_t0[next]){
comps[cur_comp].emplace_back(next);
dfs_(next, cur_comp); }
else{
comps.emplace_back(1, next);
comps.back().emplace_back(cur);
dfs_(next, comps.size()-1); } } }
ifstream f("biconex.in");
ofstream g("biconex.out");
int main(){
int n, m;
f >> n >> m;
for(int i = 0, x, y; i < m; ++i){
f >> x >> y;
vec[x].push_back(y);
vec[y].push_back(x); }
vec[0].push_back(1);
vec[1].push_back(0);
dfs(0, -1);
dfs_(0, -1);
comps.erase(begin(comps));
g << comps.size() << '\n';
for(const auto& x : comps){
for(const auto y : x) g << y << ' ';
g << '\n'; }
return 0; }