Cod sursa(job #2451885)

Utilizator nicolaee2Martinescu Nicolae nicolaee2 Data 28 august 2019 16:09:45
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,z;
int nrc;

vector<int> GF[100005],GFT[100005],G[100005];
int viz[100005];
stack<int> s;



void citire() {

   fin>>n>>m;
   for(int i=1;i<=m;i++) {

      int x,y;
      fin>>x>>y;
      GF[x].push_back(y);
      GFT[y].push_back(x);

   }

}

void DSFT(int n)
{
   viz[n]=2;
   G[nrc].push_back(n);

   for(int i=0;i<GFT[n].size();i++)
   {
      if(viz[GFT[n][i]]==1)
      {
         DSFT(GFT[n][i]);
      }
   }
}

void DFS(int n)
{
   viz[n]=1;

   for(int i=0;i<GF[n].size();i++)
   {
      if(!viz[GF[n][i]])
      {
         DFS(GF[n][i]);

      }

   }
   s.push(n);

}

void Solve() {
   for(int i=1;i<=n;i++)
   {
      if(!viz[i]) DFS(i);

   }

   while(!s.empty()) {

      int nod = s.top();

      if(viz[nod]==1)
      {
         nrc++;
         DSFT(nod);

      }
      s.pop();

   }

}

void print()
{
   cout<<nrc<<'\n';
   for(int i=1;i<=nrc;i++)
   {
      for(int j=0;j<G[i].size();j++)
         cout<<G[i][j]<<" ";
      cout<<'\n';
   }
}

int main()
{
   citire();
   Solve();
   print();


}