Cod sursa(job #2359324)

Utilizator grecubogdanGrecu Bogdan grecubogdan Data 28 februarie 2019 19:38:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[100005],GT[100005],sol2[100005];
int n,m,ctc,viz[100005],sol1[100005],k,i,x,y,nod,j;
void dfs1(int ns)
{
    int i, vecin;
    viz[ns]=1;
    for(i=0;i<G[ns].size();i++)
    {
        vecin=G[ns][i];
        if(viz[vecin]==0)
            dfs1(vecin);
    }
    k++;
    sol1[k]=ns;
}
void dfs2(int ns)
{
    int i,vecin;
    viz[ns]=2;
    sol2[ctc].push_back(ns);
    for(i=0;i<GT[ns].size();i++)
    {
        vecin=GT[ns][i];
        if(viz[vecin]==1)
            dfs2(vecin);
    }
}
int main()
{
 f>>n>>m;
 for(i=1;i<=m;i++)
 {
  f>>x>>y;
  G[x].push_back(y);
  GT[y].push_back(x);
 }
 for(i=1;i<=n;i++)
 {
     if(viz[i]==0)
        dfs1(i);
 }
 for(i=k;i>=1;i--)
 {
     nod=sol1[i];
     if(viz[nod]==1)
     {
         ctc++;
         dfs2(nod);
     }
 }
 g<<ctc<<'\n';
 for(i=1;i<=ctc;i++)
 {
     for(j=0;j<sol2[i].size();j++)
     g<<sol2[i][j]<<" ";
     g<<'\n';
 }
 return 0;
}