Cod sursa(job #928422)

Utilizator S7012MYPetru Trimbitas S7012MY Data 26 martie 2013 14:02:04
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#define DN 100005
using namespace std;

typedef vector<int>::iterator it;

int n,m,h[DN],low[DN],sz;
vector<int> gr[DN],st,cc;
bitset<DN> viz;
vector<vector<int> > r;

void dfs(int s) {
  st.push_back(s);
  viz[s]=1;
  h[s]=low[s]=++sz;
  for(it i=gr[s].begin(); i!=gr[s].end(); ++i) {
    if(!h[*i]) {
      dfs(*i);
      low[s]=min(low[s],low[*i]);
    }
    if(viz[s]) low[s]=min(low[s],low[*i]);
  }
  if(low[s]==h[s]) {
    int nod;
    for(;;) {
      nod=st.back();
      viz[nod]=0;
      cc.push_back(nod);
      st.pop_back();
      if(nod==s) break;
    }
    //cerr<<'\n';
    r.push_back(cc);
    cc.clear();
  }
}

int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>n>>m;
    for(int i=0; i<m; ++i) {
      int a,b;
      f>>a>>b;
      gr[a].push_back(b);
    }
    for(int i=1; i<=n; ++i) if(!viz[i]) dfs(i);
    g<<r.size()<<'\n';
    for(int i=0; i<r.size(); ++i) {
      for(int j=0; j<r[i].size(); ++j) g<<r[i][j]<<' ';
      g<<'\n';
    }
    return 0;
}