Cod sursa(job #2365819)

Utilizator andaraluca2001Anda Epure andaraluca2001 Data 4 martie 2019 16:40:20
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 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) dfsp(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;
}