Cod sursa(job #2646645)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 1 septembrie 2020 16:59:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define NMAX 100009
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> g[NMAX], gt[NMAX], sol[NMAX];
stack<int> H;
int uz[NMAX];
int n,m;
int nrc;
void citire();
void dfs(int k);
void dfs1(int k);
void afis();

int main()
{int i;
    citire();
 for(i=1;i<=n;i++)
    if(!uz[i])
       {nrc++;dfs(i);}
 nrc=0;
 memset(uz,0,sizeof(uz));
 while(!H.empty())
    {
     int act=H.top();
     H.pop();
     if(!uz[act])
        nrc++,dfs1(act);
    }
  afis();
    return 0;
}
void citire()
{int i,x,y;
  fin>>n>>m;
  for(i=1;i<=m;i++)
    {
      fin>>x>>y;
      g[x].push_back(y);
      gt[y].push_back(x);
    }

}
void dfs1(int k)
{
  uz[k]=nrc;
  sol[nrc].push_back(k);
  for(int i=0;i<gt[k].size();i++)
    {
     int act=gt[k][i];
     if(!uz[act])
        dfs1(act);
    }
}
void dfs(int k)
{
  int i;
  uz[k]=nrc;
  for(i=0;i<g[k].size();i++)
    {
     int vec=g[k][i];
     if(!uz[vec])
     dfs(vec);
    }
  H.push(k);
}
void afis()
{int i,j;
  fout<<nrc<<'\n';
  for(i=1;i<=nrc;i++)
    {for(j=0;j< sol[i].size();j++)
       fout<<sol[i][j]<<" ";
    fout<<'\n';
    }
}