Cod sursa(job #2366227)

Utilizator andaraluca2001Anda Epure andaraluca2001 Data 4 martie 2019 19:03:52
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX=100006;

int n,m,x,y,v[MAX],nr,nc;

bool vizs[MAX],vizp[MAX];

vector<int>s[MAX];

vector<int>p[MAX];

vector<int>cc[MAX];



ifstream in("ctc.in");

ofstream out("ctc.out");

void dfss(int x)

{

    vizs[x]=true;

    for(int i=0;i<s[x].size();i++)

    {

        int y=s[x][i];

        if(vizs[y]==false) dfss(y);

    }

    v[++nr]=x;

}



void dfsp(int x)

{



    cc[nc].push_back(x);

    vizp[x]=true;

    for(int i=0;i<p[x].size();i++)

    {

        int y=p[x][i];

        if(vizp[y]==false) dfsp(y);

    }

}

int main()

{

    in>>n>>m;



    for(int i=1;i<=m;i++)

    {

        in>>x>>y;

        s[x].push_back(y);

        p[y].push_back(x);



    }



  for(int i=1;i<=n;i++) if(vizs[i]==false) dfss(i);



  for(int i=n;i>=1;i--)
     if(vizp[v[i]]==false)
     {
         ++nc;
         dfsp(v[i]);
     }


  out<<nc<<'\n';

  for(int i=1;i<=nc;i++)

  {

      for(int j=0;j<cc[i].size();j++) out<<cc[i][j]<<" ";

      out<<'\n';

  }



    return 0;

}