Cod sursa(job #2311012)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 2 ianuarie 2019 15:08:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;

int low[100001], disc[100001], TT[100001];
bool AP[100001], viz[100001];
int n, m, x, y;
vector<int>G[100001], SOL[100001];
stack<pair<int, int>>ST;
int timp, nsol;

inline void DFS(int nod)
{
    int children=0;
    viz[nod]=1;
    disc[nod]=low[nod]=++timp;
    for(auto it:G[nod])
    {
        if(!viz[it])
        {
            ST.push(make_pair(nod, it));
            ++children;
            TT[it]=nod;
            DFS(it);
            low[nod]=min(low[nod], low[it]);
            if((TT[nod]==-1 && children>=2) || (TT[nod]!=-1 && low[it]>=disc[nod]))
            {
                int a, b;
                ++nsol;
                do
                {
                    a=ST.top().first;
                    b=ST.top().second;
                    ST.pop();
                    SOL[nsol].push_back(b);
                }while(a!=nod && b!=it);
                SOL[nsol].push_back(a);
            }
        }
        else if(it!=TT[nod])
        {
            low[nod]=min(low[nod], disc[it]);
        }
    }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DFS(1);
    printf("%d\n", nsol);
    for(int i=1; i<=nsol; ++i)
    {
        sort(SOL[i].begin(), SOL[i].end());
        for(auto it:SOL[i]) printf("%d ", it);
        printf("\n");
    }
    return 0;
}