Cod sursa(job #1028179)

Utilizator lucianRRuscanu Lucian lucianR Data 13 noiembrie 2013 19:02:14
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#define N_MAX 100001
#define M_MAX 200001

using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");

vector <int> v[N_MAX];
bool visited[N_MAX];
int cc = 0, N, M, st[2][M_MAX], L[N_MAX], s, ss, bc[N_MAX / 2][100], b, pst[N_MAX];

void DFS(int node)
{
    /*cout<<endl<<"S:"<<s<<endl;
    for(int i = 0; i < s; i++)
        cout << st[0][i] << st[1][i];*/
    for(int i = 0; i < v[node].size(); i++)
    {
        //cout<<ss<<endl;
        if(visited[v[node][i]] && L[v[node][i]] < L[node] - 1)
        {
            int bb = 1;
            //cout<<"DA";
            ss = pst[v[node][i]];
            while(st[1][ss] != node)
            {
                //cout<<"SS"<<ss;
                bc[b][bb++] = st[0][ss++];
                st[0][ss - 1] = 0;
                st[1][ss - 1] = 0;
                if(st[1][ss] == node){ bc[b][bb++] = st[0][ss]; bc[b][bb] = st[1][ss]; st[0][ss] = 0;}
            }
            st[1][ss] = 0;
            //bc[b][bb] = st[1][ss-1];
            bc[b][0] = bb;
            b++;
        }
        if(!visited[v[node][i]])
        {
            L[v[node][i]] = L[node] + 1;
            st[0][s] = node;
            pst[node] = s;
            st[1][s++] = v[node][i];
            visited[v[node][i]] = true;
            DFS(v[node][i]);
        }
        //if(i == v[node].size() - 1) ass--;
    }
}

int main()
{
    in >> N >> M;
    for(int i = 0; i < M; i++)
    {
        int x, y;
        in >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    visited[1] = 1;
    L[1] = 1;
    pst[1] = 0;
    ss = s;
    DFS(1);
    for(int i = 0; i < s; i++)
    {
        while(st[0][i] == 0)
            i++;
        if(st[0][i] != 0)
        {
            int bb = 1;
                bc[b][bb++] = st[0][i];
                bc[b][bb] = st[1][i];


            bc[b][0] = bb;
            b++;
        }
    }
    out << b <<"\n";
    for(int i = 0; i < b; i++)
    {
        for(int j = 1; j <= bc[i][0]; j++)
            out << bc[i][j] << " ";
        out<<"\n";
    }
    return 0;
}