Cod sursa(job #1882512)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 17 februarie 2017 11:44:57
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#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; }