Cod sursa(job #894716)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 26 februarie 2013 23:07:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<fstream>
#include<algorithm>
#include<vector>
#define NMAX 100010

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<int> a[NMAX], at[NMAX], rez[NMAX];

int n, m, vz[NMAX], vzt[NMAX], x[NMAX], nr, nctc;

void Citeste()
{
    int x, y;

    f>>n>>m;

    while (m--)
    {
        f>>x>>y;
        a[x].push_back(y);
        at[y].push_back(x);
    }
}

void DFS(int nod)
{
    int i;

    vz[nod]=m;
    for (i=0; i<a[nod].size(); ++i)
        if (!vz[a[nod][i]])
            DFS(a[nod][i]);

    x[++nr]=nod;
}

void DFST(int nod)
{
    int i;

    if (vz[nod]==m)
    {
        vzt[nod]=m;
        rez[nctc].push_back(nod);

        for (i=0; i<at[nod].size(); ++i)
            if (!vzt[at[nod][i]]) DFST(at[nod][i]);
    }
}

void Solve()
{
    int i, j;
    m=0;

    for (i=1; i<=n; ++i)
        if (!vz[i])
        {
            ++m; nr=0;
            DFS(i);

            for (i=nr; i>0; --i)
                if (!vzt[x[i]])
                {
                    ++nctc;
                    DFST(x[i]);
                }

        }
    g<<nctc<<"\n";
    for (i=1; i<=nctc; ++i)
    {
        sort(rez[i].begin(), rez[i].end());
        for (j=0; j<rez[i].size(); ++j) g<<rez[i][j]<<" ";
        g<<"\n";
    }
}

int main()
{
    Citeste();
    Solve();
    f.close();
    g.close();
    return 0;
}