Cod sursa(job #1111747)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 19 februarie 2014 08:49:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
//Componente tare conexe - O(N+M)
#include<fstream>
#include<bitset>
#include<vector>
#define Nmax 100099
#define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int N,M,sol,Tsort[Nmax],x,y;
bitset < Nmax> viz;
vector < int > G[Nmax],T[Nmax],CT[Nmax];

void ReadInput()
{
     f>>N>>M;
     for(int i=1;i<=M;++i)
          f>>x>>y , G[x].pb(y) , T[y].pb(x);
}

void PrintOutput()
{
     g<<sol<<'\n';
     for(int i=1;i<=sol;++i,g<<'\n')
          for(vector<int>::iterator it=CT[i].begin();it!=CT[i].end();++it)
               g<<*it<<' ';
}

void DFS(int node)
{
     viz[node]=1;
     for(vector<int>::iterator it=G[node].begin();it!=G[node].end();++it)
          if(!viz[*it])DFS(*it);
     Tsort[++Tsort[0]]=node;
}

void DFS_T(int node)
{
     viz[node]=0 ; CT[sol].pb(node);
     for(vector<int>::iterator it=T[node].begin();it!=T[node].end();++it)
          if(viz[*it])DFS_T(*it);
}

void Tarjan()
{
     for(int i=1;i<=N;++i)
          if(!viz[i])DFS(i);
     for(int i=N;i>=1;--i)
          if(viz[Tsort[i]])
          {
               ++sol;
               DFS_T(Tsort[i]);
          }
}
int main()
{
     ReadInput();
     Tarjan();
     PrintOutput();
     f.close();g.close();
     return 0;
}