Cod sursa(job #1232495)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 22 septembrie 2014 22:45:17
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#define NMAX 100002
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
int timp[NMAX], n, nr, i, p, j, num, u ,v, sol[NMAX], m, rez[NMAX];
bool viz[NMAX];
vector<int> g[NMAX], gt[NMAX];
void DFSg (int u)
{
    for (int i=0; i<g[u].size(); i++)
    {
        if(!viz[g[u][i]])
        {
            viz[g[u][i]]=1;
            DFSg(g[u][i]);
        }

    }
    timp[++num] = u;
}
void DFSgt (int u)
{   m++;
    sol[m]=u;
    for (int i=0; i<gt[u].size(); i++)
    {
        if(!viz[gt[u][i]])
        {
            viz[gt[u][i]]=1;
            //rez[p].push_back(gt[u][i]);
            DFSgt(gt[u][i]);

        }
    }
}

int main()
{
    in>>n>>nr;
    for (i=1; i<=nr; i++)
    {
        in>>u>>v;
        g[u].push_back(v);
        gt[v].push_back(u);
    }
    for (i=1; i<=n; i++)
        if (!viz[i])
        {
            viz[i]=1;
            DFSg(i);
        }

    /* for (i=1; i<=n; i++)
     {

         sort(gt[i].begin(),gt[i].end(),cmp);
     }*/
    memset(viz,0,sizeof(viz));
    for (i=n; i>=1; i--)
    {
        if (!viz[timp[i]])
        {   p++;
            rez[p]=m+1;
            viz[timp[i]]=1;
            //p++;
            //rez[p].push_back(i);
            DFSgt(timp[i]);

        }
    }
    out<<p<<'\n';
    for (i=1; i<=p; i++)
    {
        for (j=rez[i]; j<rez[i+1]; j++)
            out<<sol[j]<<' ';
        out<<'\n';
    }
    return 0;
}