Cod sursa(job #2205811)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 20 mai 2018 13:05:39
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
#define N 100002
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, nbix, d[N], low[N];
vector <int> graph[N];
vector <int> bix[N];
stack <int> st;
void dfs(int node, int dad)
{
    d[node]=low[node]=d[dad]+1;
    st.push(node);
    for(auto i : graph[node]){
        if(i==dad) continue;
        if(d[i]!=0){
            low[node]=min(low[node],d[i]);
            continue;
        }
        dfs(i,node);
        low[node]=min(low[node],low[i]);
        if(d[node]<=low[i]) ///node punct de articulatie
        {
            nbix++;
            int k;
            do{
                k=st.top();
                bix[nbix].push_back(k);
                st.pop();
            }while(k!=i);
            bix[nbix].push_back(node);
        }
    }
}
int main()
{
    int i, j;
    fin>>n>>m;
    while(m--){
        fin>>i>>j;
        graph[i].push_back(j);
        graph[j].push_back(i);
    }
    for(i=1; i<=n; i++)
        if(d[i]==0) dfs(i,0);
    fout<<nbix<<'\n';
    for(i=1; i<=nbix; i++)
    {
        for(auto j : bix[i]) fout<<j<<' ';
        fout<<'\n';
    }
    return 0;
}