Cod sursa(job #936295)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 6 aprilie 2013 17:33:32
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
using namespace std;
ifstream f("ctc.in");ofstream g("ctc.out");
#include <vector>
#define LE 100666
vector<int> g1[LE],g2[LE];
bool viz[LE];
int cul[LE];
#define pb push_back
int color,i,j,k,xx,yy,n,m;
vector<int> st[LE];

void dfs(int nod,int col){
  if (viz[nod]==true||cul[nod]==col) return;
  int N=g1[nod].size(),i; cul[nod]=col;

  for(i=0;i<N;++i)
    dfs(g1[nod][i],col);
}
void dfs2(int nod,int col2){
  if (viz[nod]==true||cul[nod]==col2) return;
  int N=g2[nod].size(),i;
  if (cul[nod]==col2-1) {viz[nod]=true;st[k].pb(nod);}

  for(i=0;i<N;++i)
    dfs2(g2[nod][i],col2);
}
int main(){

    f>>n>>m;
    for(i=1;i<=m;++i){
     f>>xx>>yy;
     g1[xx].pb(yy);g2[yy].pb(xx);
    }

    for(i=1;i<=n;++i) if (viz[i]==false){
      ++k;
      dfs(i,(++color));
      dfs2(i,(++color));
    }
    g<<k<<'\n';

    for(i=1;i<=k;++i){
      int N=st[i].size();
      for(j=0;j<N;++j) g<<st[i][j]<<" ";
      g<<'\n';
    }

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