Cod sursa(job #1130024)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 28 februarie 2014 10:53:17
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#include <bitset>
#define Nmax 100009
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int N,M,x,y,sol,Tsort[Nmax];

vector < int > G[Nmax],T[Nmax],CTC[Nmax];
bitset < Nmax > viz_T,viz;

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 DFS2(int node)
{
     viz_T[node]=1; CTC[sol].push_back(node);
     for(vector < int >::iterator it=T[node].begin();it!=T[node].end();++it)
          if(!viz_T[*it])
          DFS2(*it);

}

int main()
{
     f>>N>>M;
     for(int i=1;i<=M;++i)
     {
          int x,y;
          f>>x>>y;
          G[x].push_back(y) ,T[y].push_back(x);
     }
     for(int i=1;i<=N;++i)
          if(!viz[i])DFS(i);
     for(int i=Tsort[0] ; i ; --i)
          if(!viz_T[Tsort[i]])++sol,DFS2(Tsort[i]);
     g<<sol<<'\n';
     for(int i=1;i<=sol;++i,g<<'\n')
          for(int j=0;j<CTC[i].size();++j)g<<CTC[i][j]<<' ';
     f.close();g.close();
     return 0;
}