Cod sursa(job #1882125)

Utilizator popescu.octavianPopescu Octavian popescu.octavian Data 16 februarie 2017 23:04:32
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define pb push_back
#define NMax 100010
#define MMax 200010
#define nod pair<int, int>

using namespace std;

vector<int> G[NMax], v[NMax];

int n, m, a, b, i, j, low[NMax], niv[NMax], ap[NMax], nrsol, varf;

struct muchie
{
    int x, y;
} st[MMax];

void DFS (int nod, int nivel, int tata)
{
    ap[nod]=1; niv[nod]=nivel; low[nod]=nivel;

    for(int i=0; i<G[nod].size(); i++)
    {
        int fiu=G[nod][i];

        if(tata!=fiu)
        {
            if(!ap[fiu])
            {
                ++varf;
                st[varf].x=nod; st[varf].y=fiu;

                DFS(fiu, nivel+1, nod);

                if(low[fiu]>=nivel)
                {
                    ++nrsol;
                    v[nrsol].pb(nod);

                    while(st[varf].x!=nod)
                    {
                        v[nrsol].pb(st[varf].y);
                        varf--;
                    }

                    v[nrsol].pb(fiu);
                    varf--;
                }
                low[nod]=Min(low[nod], low[fiu]);
            }
            else low[nod]=Min(low[nod],niv[fiu]);
        }
    }
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++)
    {
        scanf("%d %d", &a, &b);
        G[a].pb(b);
        G[b].pb(a);
    }
    DFS(1, 1, 0);

    for(i=1; i<=nrsol; i++)
    {
        for(j=0; j<v[i].size(); j++)
            printf("%d ", v[i][j]);
        printf("\n");
    }
    return 0;
}