Cod sursa(job #1589667)

Utilizator robertstrecheStreche Robert robertstreche Data 4 februarie 2016 11:57:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <bitset>
#include <vector>

#define NMAX 100005

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

bitset <NMAX>ap;
vector <int>ordine,sol[NMAX];
vector <int>in[NMAX],out[NMAX];

int m,n,nr,x,y;

void dfs1(int nod){
  ap[nod]=1;
  for (auto it:out[nod])if (!ap[it])
    dfs1(it);

  ordine.push_back(nod);
}
void dfs2(int nod){
  ap[nod]=0;
  for (auto it:in[nod])if (ap[it]){
    sol[nr].push_back(it);
    dfs2(it);
  }
}
int main()
{
    f>>n;
    for (f>>m;m;m--){
        f>>x>>y;
        in[y].push_back(x);
        out[x].push_back(y);
    }
    for (int i=1;i<=n;i++)if (!ap[i])
        dfs1(i);

    for (;!ordine.empty();ordine.pop_back())if (ap[ordine.back()]){
        sol[++nr].push_back(ordine.back());
        dfs2(ordine.back());
    }
    g<<nr<<'\n';

    for (int i=1;i<=nr;i++,g<<'\n')
      for (auto it:sol[i])g<<it<<" ";

    f.close();
    g.close();
}