Cod sursa(job #1184539)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 13 mai 2014 06:42:02
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;

const int dim = 100005;

int N, M, NCTC, dfn[dim], low[dim], index;
vector <int> CTC[dim], V[dim];
stack <int> S;

void ctc (int n, int t)
{
    S.push(n);
    dfn[n] = low[n] = ++index;

    for (int i = 0, f; i < V[n].size(); i++)
    {
        f = V[n][i];
        if (f == t) continue;

        if (dfn[f] == 0)
        {
            ctc (f, n);

            low[n] = min (low[n], low[f]);
        }
        else
        {
            low[n] = min (low[n], dfn[f]);
        }
    }

    if (low[n] == dfn[n])
    {
        NCTC++;
        int last;
        do
        {
            last = S.top();
            S.pop ();
            CTC[NCTC].push_back (last);
        } while (last != n);
    }
}

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

    scanf ("%d%d", &N, &M);

    for (int i = 1, a, b; i <= M; i++)
    {
        scanf ("%d%d", &a, &b);
        V[a].push_back (b);
        V[b].push_back (a);
    }

    for (int n = 1; n <= N; n++)
    {
        if (dfn[n] == 0)
        {
            ctc (n, 0);
        }
    }

    printf ("%d\n", NCTC);
    for (int c = 1, i, n; c <= NCTC; c++)
    {
        for (i = 0; i < CTC[c].size(); i++)
        {
            n = CTC[c][i];
            printf ("%d ", n);
        }
        printf ("\n");
    }

    return 0;
}