Cod sursa(job #1589615)

Utilizator robertstrecheStreche Robert robertstreche Data 4 februarie 2016 11:13:45
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 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]){
    ordine.push_back(it);
    dfs1(it);
  }
}
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]){
        ordine.push_back(i);
        dfs1(i);
    }
    for (auto it:ordine)if (ap[it]){
        sol[++nr].push_back(it);
        dfs2(it);
    }
    g<<nr<<'\n';

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

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