Cod sursa(job #2314924)

Utilizator mateialexandru25Matei Alexandru mateialexandru25 Data 9 ianuarie 2019 11:38:23
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 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]; /// liste adiacenta graf G
vector <int> GT[N]; /// liste adiacente graf transpus
vector <int> CTC[N]; /// memorarea componentelor tare conexe

stack <int> S; /// nodurile in ordinea timpilor de final

bool viz[N];   /// DFS pe graful G
bool vizt[N]; /// DFS pe graful GT

int nc; /// numarul de componente tare conexe

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);
     }
   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 TimpiFinali()
{ int i;
  for(i=1;i<=n;++i)
     if(!viz[i]) DFS(i);
}

void DFST(int x)
{ vizt[x]=1;
  CTC[nc].push_back(x);
  for(int i=0; i<GT[x].size();++i)
       if(!vizt[GT[x][i]])
            DFST(GT[x][i]);
}

void ComponenteTareConexe()
{ int x;
  while(!S.empty())
    { x=S.top(); S.pop();
      if(!vizt[x])
         { nc++;
           DFST(x);
         }
    }
}

void Afisare()
{ int i,j;
  fout<<nc<<"\n";
  for(i=1;i<=nc;i++)
    { for(j=0;j<CTC[i].size();++j)
           fout<<CTC[i][j]<<" ";
      fout<<"\n";
    }
}

int main()
{ Citire();
  TimpiFinali();
  ComponenteTareConexe();
  Afisare();
  return 0;
}