Cod sursa(job #2174948)

Utilizator infomaxInfomax infomax Data 16 martie 2018 14:23:57
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

ifstream F("biconex.in");
ofstream G("biconex.out");

int n, m, niv[100005], low[100005], x, y, k;
bitset<100005> v;
stack<int> st;
vector<int> a[100005], ans[100005];

void dfs(int x, int t, int Niv){
    v[x]=1;
    st.push(x);
    low[x]=niv[x]=Niv;
    for(auto it:a[x]){
        if(it==t) continue;
        if(v[it]){
            low[x]=min(low[x], niv[it]);
            continue;
        }
        dfs(it, x, Niv+1);
        low[x]=min(low[x], low[it]);
        if(low[it]>=niv[x]){
            k++;
            do{
                y=st.top(); st.pop();
                ans[k].push_back(y);
            }while(y!=it);
            ans[k].push_back(x);
        }
    }
}

int main()
{
    F >> n >> m;
    for(int i = 1; i <= m; ++ i){
        F >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1, 0, 1);
    G << k << '\n';
    for(int i = 1; i <= k; ++ i, G << '\n')
        for(auto it:ans[i])
            G << it << " ";
    return 0;
}