Cod sursa(job #250997)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 1 februarie 2009 15:45:26
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
# include <cstdio>
# include <vector>

using namespace std;

# define FIN "biconex.in"
# define FOUT "biconex.out"
# define min(a, b) (a < b ? a : b)
# define MAXN 100005

int N, M, i, cnt, comp;
int s[MAXN];
int Up[MAXN];
int Lvl[MAXN];
vector <int> E;
vector <int> G[MAXN];
vector <int> C[MAXN];

    void find_Cb(int nod, int pap, int niv)
    {
        int x, y;
        vector <int> :: iterator it;

        Lvl[nod] = Up[nod] = niv;
        for (it = G[nod].begin(); it < G[nod].end(); ++it)
        {

            if (*it == pap) continue;
            if (!Lvl[*it])
            {
                 E.push_back(nod);
                 E.push_back(*it);

                 find_Cb(*it, nod, niv + 1);

                 Up[nod] = min(Up[nod], Up[*it]);

                 if (Up[*it] >= Lvl[nod])
                 {
                     int x = 0, y;

                     ++comp;
                     do
                       {
                          y = x;
                          x = *(E.end() - 1);
                          E.pop_back();

                          if (s[x] != comp) C[comp].push_back(x);
                          s[x] = comp;
                       }
                     while (x != nod || y != *it);
                 }
            }
            else Up[nod] = min(Up[nod], Lvl[*it]);
        }
    }

    void print()
    {
        int i;
        vector <int> :: iterator it;


        printf("%d\n",comp);
        for (i = 1; i <= comp; ++i)
        {
            for (it = C[i].begin(); it != C[i].end(); ++it)
              printf("%d ",*it);
            printf("\n");
        }
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);

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

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

        cnt = comp = 0;
        find_Cb(1, 0, 1);

        print();

        return 0;
    }