Cod sursa(job #2299907)

Utilizator 3DwArDPauliuc Edward 3DwArD Data 10 decembrie 2018 15:23:47
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

vector< vector< int > > G;
int n,m;
void citire(){
    f>>n>>m;
    G.resize(n+2);
    for(int i=1,x,y;i<=m;i++){
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
vector<int> lvl(NMAX),low(NMAX);
int pasi,nrcomp;
stack< pair<int,int> > q;
vector<int> componente[NMAX];
void DFS(int node){
    lvl[node] = low[node] = ++pasi;
    for(auto it: G[node]){
        if(!lvl[it]){
            q.push(make_pair(node,it));
            DFS(it);
            low[node] = min(low[node], low[it]);
            if(low[it]>=lvl[node]){
                nrcomp++;
                while(q.top().first!=node)
                    componente[nrcomp].push_back(q.top().second),
                    q.pop();
                componente[nrcomp].push_back(q.top().first);
                componente[nrcomp].push_back(q.top().second);
                q.pop();
                sort(componente[nrcomp].begin(),componente[nrcomp].end());
            }
        }
        else low[node]=min(low[node],lvl[it]);
    }
}
void afisare(){
    g<<nrcomp<<"\n";
    for(int i=1;i<=nrcomp;i++)
        {for(auto it:componente[i])
            g<<it<<" ";
        g<<"\n";
    }
}

int main()
{
    citire();
    for(int i=1;i<=n;i++)
        if(!lvl[i])
            DFS(i);
    afisare();
    return 0;
}