Cod sursa(job #2175356)

Utilizator dumitrescu_andreiDumitrescu Andrei dumitrescu_andrei Data 16 martie 2018 16:49:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n,m,nr,VfS,nrfii,bic;
vector <int> V[100005];
int low[100005],dfn[100005];
stack <int> S;
vector <int> G[100005];
int da[100005];

void DFS(int nod,int tata)
{
    S.push(nod);
    dfn[nod]=low[nod]=++nr;
    for(auto &it:V[nod])
    {
        if(it==tata)
            continue;
        if(dfn[it]==-1)
        {
            DFS(it,nod);
            low[nod]=min(low[nod],low[it]);
            if(low[it]>=dfn[nod])
            {
              bic++;
              G[bic].push_back(nod);
              int y;
              do{
                y=S.top();
                S.pop();
                G[bic].push_back(y);
              }while(y!=it);

            }
        }
        else
        {
            low[nod]=min(low[nod],dfn[it]);
        }
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        f>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    memset(dfn,-1,sizeof(dfn));
    memset(low,-1,sizeof(low));
    DFS(1,0);
    g<<bic<<'\n';
    for(int i=1;i<=bic;++i,g<<'\n')
        for(auto &it:G[i])
            g<<it<<" ";
    return 0;
}