Cod sursa(job #1232429)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 22 septembrie 2014 20:29:03
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#define NMAX 100 001
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
int timp[NMAX], t, n, nr, i, p, j, u ,v;
bool cmp(int x,int y)
{
    return timp[x]>timp[y];
}
bool viz[NMAX];
vector<int> g[NMAX], gt[NMAX] ,rez[NMAX];
int DFSg (int u)
{
    int i=0;
    viz[u]=1;
    t++;
    for (i=0; i<g[u].size(); i++)
    {
        if(!viz[g[u][i]]) DFSg(g[u][i]);

    }
    timp[u] = ++t;
}
int DFSgt (int u)
{
    int i=0;
    viz[u]=1;
    //rez.push_back(u);
    for (i=0; i<gt[u].size(); i++)
    {
        if(!viz[gt[u][i]])
        {
            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])
            DFSg(i);

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

        sort(gt[i].begin(),gt[i].end(),cmp);
    }
    memset(viz,0,sizeof(viz));
  // out<<p-1<<'\n';
  p=0;
    for (i=1; i<=n; i++)
    {
        if (!viz[i])
        {   p++;
            rez[p].push_back(i);
            DFSgt(i);
            //p++;
            //for (int j=0; j<rez.size(); j++)
            //out<<rez[j]<<' ';
           //out<<'\n';
        }
       //rez.clear();


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