Cod sursa(job #1453436)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 23 iunie 2015 15:20:08
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;

vector<int> g[100005], gt[100005], comp[100005];
int i,j,n,m,x,y,k;
int st[100005],lev;
bool viz[100005];

void dfs(int nod) {

   viz[nod]=1;

   for (int i=0; i<g[nod].size(); ++i)
    if (viz[g[nod][i]]==0) dfs(g[nod][i]);

   st[++lev]=nod;

}

void dfs2(int nod) {

   viz[nod]=1;
   comp[k].push_back(nod);

   for (int i=0; i<gt[nod].size(); ++i)
    if (viz[gt[nod][i]]==0) dfs(gt[nod][i]);

}

int main(void){

   ifstream cin("ctc.in");
   ofstream cout("ctc.out");

   cin>>n>>m;

   for (i=1; i<=m; ++i) {
      cin>>x>>y;
      g[x].push_back(y);
      gt[y].push_back(x);
   }

   for (i=1; i<=n; ++i)
    if (viz[i]==0) dfs(i);

   memset(viz,0,sizeof(viz));

   for (i=lev; i>=1; --i)
   if (viz[i]==0) { ++k; dfs2(i); }

   cout<<k<<"\n";

   for (i=1; i<=k; ++i){

      for (j=0; j<comp.size(); ++j) cout<<comp[i][j]<<" ";

      cout<<"\n";

   }

  return 0;
}