Cod sursa(job #2176234)

Utilizator Constantin.Dragancea Constantin Constantin. Data 16 martie 2018 21:45:52
Problema Componente biconexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
#define N 100010

ifstream fin ("biconex.in");
ofstream fout ("biconex.out");

int n, m, low[N], viz[N], k, ans, cnt, AP[N];
vector <int> v[N];

void dfs(int q, int pr){
    low[q] = viz[q] = ++k;
    for (auto it: v[q]){
        if (it == pr) continue;
        if (!viz[it]){
            if (q == 1) cnt++;
            dfs(it, q);
            low[q] = min(low[q], low[it]);
            if (low[it] >= viz[q]){
                if (!AP[q]) ans++;
                AP[q]++;
            }
        }
        else low[q] = min(low[q], viz[it]);
    }
}

void dfsafis(int q, int src){
    viz[q] = 1;
    if (q != src) fout << q << " ";
    if (AP[q] && q != src) return;
    for (auto it: v[q]){
        if (!viz[it]){
            if (q == src) fout << "\n" << q << " ";
            dfsafis(it, src);
        }
    }
}

int main(){
    fin >> n >> m;
    for (int i=1; i<=m; i++){
        int x, y;
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, -1);
    AP[1] = cnt - 1;
    for (int i=1; i<=n; i++) viz[i] = 0;
    fout << ans + 1;
    for (int i=1; i<=n; i++){
        if (AP[i]) dfsafis(i, i);
    }
    return 0;
}