Cod sursa(job #249706)

Utilizator Mishu91Andrei Misarca Mishu91 Data 28 ianuarie 2009 23:47:31
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_N 100005
#define x first
#define y second
#define foreach(V) for(typeof V.begin() it = V.begin(); it != V.end(); ++it)

int N, M;
vector<int> C[MAX_N];
vector<int> G[MAX_N];
stack<pair<int, int> > S;
int dfn[MAX_N], low[MAX_N];
int Nrc;

void citire()
{
    scanf("%d %d",&N, &M);

    for(int i = 1; i <= M; ++i)
    {
        int x, y;
        scanf("%d %d",&x, &y);

        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void search(int x, int y)
{
    ++Nrc;
    vector <int> aux;
    int tx, ty;

    do
    {
        tx = S.top().x, ty = S.top().y;
        S.pop();
        aux.push_back(tx);
        aux.push_back(ty);
    }
    while(tx != x || ty != y);

    sort(aux.begin(), aux.end());

    C[Nrc].push_back(aux[0]);

    for(int i = 1; i != aux.size(); ++i)
        if(aux[i] != aux[i-1])
            C[Nrc].push_back(aux[i]);
}

void DF(int n, int ant, int nr)
{
    dfn[n] = low[n] = nr;

    foreach(G[n])
    {
        int nod = *it;
        if(nod == ant) continue;
        if(dfn[nod] == -1)
        {
            S.push(make_pair(n, nod));
            DF(nod, n, nr+1);
            low[n] = min(low[n], low[nod]);
            if(low[nod] >= dfn[n])
                search(n, nod);
        }
        else
            low[n] = min(low[n], dfn[nod]);
    }
}

int main()
{
    freopen("biconexe.in","rt",stdin);
    freopen("biconexe.out","wt",stdout);

    citire();
    memset(dfn, -1, sizeof dfn);

    DF(1, 0, 0);

    printf("%d\n",Nrc);
    for(int i = 1; i <= Nrc; ++i)
    {
        foreach(C[i])
            printf("%d ",*it);
        printf("\n");
    }
}