Cod sursa(job #2314929)

Utilizator MirunaStefaniaLupascu Miruna-Stefania MirunaStefania Data 9 ianuarie 2019 11:41:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m;
vector <int> G[N],Gt[N];
vector <int> CTC[N]; ///elem componentelor
stack <int> S;
int ct; //nr comp
int vf;
bool viz[N],vizt[N]; ///dfs pe ambele
void Read()
{  int x,y;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);  //graf transpus
    }
   fin.close();
}
void DFS(int x)
{  viz[x]=1;
  for(int i=0;i<G[x].size();i++)
   if(!viz[G[x][i]])
    DFS(G[x][i]);

 S.push(x);
}
void DFSt(int x)
{
    vizt[x]=1;
    CTC[ct].push_back(x);
    for(int i=0;i<Gt[x].size();i++)
        if(!vizt[Gt[x][i]])
        DFSt(Gt[x][i]);

}
void Do()
{
    while(!S.empty())
    { vf=S.top(); S.pop();

      if(!vizt[vf]) { ct++; DFSt(vf); }

    }
}
void Timpi()
{
    for(int i=1;i<=n;i++)
        if(!viz[i]) DFS(i);
}
void Write()
{   fout<<ct<<"\n";
    for(int i=1;i<=n;i++)
        {for(int j=0;j<CTC[i].size();j++)
         fout<<CTC[i][j]<<" ";
         fout<<"\n";
        }
fout.close();
}
int main()
{
   Read();
   Timpi();
   Do();
   Write();

    return 0;
}